Branches History Index

◀ ▲ ▶Branches / Theoretical-computer-science / Formal-languages / Definition: Type-0 (Phrase Structure) Grammars and Recursively Enumerable Languages

Definition: Type-0 (Phrase Structure) Grammars and Recursively Enumerable Languages

Every grammar $G=(V,T,R,S)$ with no restrictions whatsoever besides the restrictions given1 in the definition of a grammar is a type-0, or phrase-structure grammar. Formal languages generated by type-0 grammars are called recursively enumerable.2

Mentioned in:

Explanations: 1

Thank you to the contributors under CC BY-SA 4.0!

Github:
bookofproofs

References

Bibliography

  1. Erk, Katrin; Priese, Lutz: "Theoretische Informatik", Springer Verlag, 2000, 2nd Edition
  2. Hoffmann, Dirk: "Theoretische Informatik, 3. Auflage", Hanser, 2015

Footnotes

  1. A grammar has only finitely many rules, and every premise of a rule contains at least one variable. ↩

  2. We will see later (when we will be talking about automata) that such languages are recognized/accepted by Turing Machines, therefore, they are also called Turing-acceptable or Turing-recognizable. ↩