China
Africa
Explore chapters and articles related to this topic
Introduction
Published in John N. Mordeson, Davender S. Malik, Fuzzy Automata and Languages, 2002
John N. Mordeson, Davender S. Malik
Grammars are classified according to the form of the production rules used (Chomsky hierarchy). These grammars are sometimes described as follows: Unrestricted or type 0 grammars have no restrictions on the form of the rules. Context-sensitive or type 1 grammars require that if x→y is a production, then the length of the string x, denoted by |x|, must be not greater than the length |y| of the string y. A grammar is said to be context-free or type 2 if every production is of the form A→y, where A∈N. A grammar is said to be regular (left linear) if all its productions are of the form A→B,A→b, or A→bB, where A,B∈N and b∈T. It is sometimes useful to write a grammar in a particular form. Two forms for context-free grammars have been commonly used: Chomsky normal form and Greibach normal form. A context-free grammar is said to be in Chomsky normal form if every production rule is one of the form A→BC or A→a, where A,B,C∈N and a∈T. Also, if Λ∈L(G), the language generated by G, then s→Λ is a production and s does not appear on the right-hand side of any production. A context-free grammar is said to be in Greibach normal form if every production rule is of the form A→az, where A∈N,a∈T, and z∈N*. Also, if Λ∈L(G), then s→Λ is a production and s does not appear on the right-hand side of any production.
Coding-theorem like behaviour and emergence of the universal distribution from resource-bounded algorithmic probability
Published in International Journal of Parallel, Emergent and Distributed Systems, 2019
Hector Zenil, Liliana Badillo, Santiago Hernández-Orozco, Francisco Hernández-Quiroz
The Chomsky hierarchy is a strict containment hierarchy of classes of formal grammars equivalent to different computational models of increasing computing power. At each of the 4 levels, grammars and automata compute a larger set of possible languages and strings. The four levels, from weaker to stronger computational power, are:The most restricted grammars generating the regular languages. They consist of rules with single non-terminal symbols on the left-hand side and strings of terminal symbols followed by at most one non-terminal symbol on the right-hand side. These types of rule are referred to as right linear (but a symmetrical left linear definition works as well). This level is studied by way of finite-state transducers (FST), a generalisation of finite-state automata (FSA) that produce an output at every step, generating a relation between input strings and output strings. Though apparently more general, FST-recognised languages are the same as FSA-accepted sets. Hence both can represent this level. We use an enumeration of transducers introduced in [24] where they also proved an invariance theorem [1,2,28], thus demonstrating that the enumeration choice is invariant (up to a constant).Grammars that generate the context-free languages. These kinds of grammars are extensively used in linguistics. The languages generated by CFG grammars are exactly the languages that can be recognized by a non-deterministic pushdown automaton. We denote this level by CFG. We generated production rules for 40,000 grammars according to a sound scheme introduced in [25].Grammars that generate the context-sensitive languages. The languages described by these grammars are all languages that can be recognized by a linear-bounded automaton (LBA), a Turing machine whose tape’s length is bounded by a constant times the length of the input. An AP-based variation is introduced here, and we denote it by LBA/AP.The least restricted grammar. Generates the languages that can be recognized by Turing machines, also called recursively enumerable languages. This is the level at which Turing-universality is achieved or required. We used previously generated distributions produced and reported in [26,27]We also explore the consequences of relaxing the halting configuration (e.g. halting state) in models of universal computation (Type-0) when it comes to comparing their output distributions.