Greibach's theorem, proved by the computer scientist Sheila Greibach in 1963, is a result in formal language theory establishing that a range of properties of formal language classes, including classes defined by context-free and context-sensitive grammars, are undecidable, meaning no algorithm can determine in general whether a given language has the property. The theorem is a key source of undecidability results in the theory of formal languages, used to show that many natural questions about a language generated by a grammar cannot be answered mechanically for grammars in general.
Facts
StatementGreibach's theorem states that certain properties of formal language classes are undecidable, meaning no algorithm can determine in general whether a language belonging to a given class has that property. 1 Sources
1. Greibach's theorem, Wikipedia
Lede section, first sentence
Greibach's theorem states that certain properties of formal language classes are undecidable.
Lede section, second sentence
It is named after the computer scientist Sheila Greibach, who first proved it in 1963.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.