patternMinor
Language containing all unambiguous grammars
Viewed 0 times
containingallgrammarsunambiguouslanguage
Problem
Suppose $L$ is the language of the unambiguous grammars. That is, a sentence $w\in{}L$ if it is a string that describes an unambiguous context-free grammar.
Considering that deciding whether a context-free grammar is ambiguous is non-decidable, would it be correct to say that $L$ exists but is not recursively enumerable?
Considering that deciding whether a context-free grammar is ambiguous is non-decidable, would it be correct to say that $L$ exists but is not recursively enumerable?
Solution
The language $L$ clearly exists — you just defined it!
It’s not hard to check that your language is co-r.e., that is, you can enumerate ambiguous grammars. Since it’s not recursive, it cannot be r.e.
It’s not hard to check that your language is co-r.e., that is, you can enumerate ambiguous grammars. Since it’s not recursive, it cannot be r.e.
Context
StackExchange Computer Science Q#114694, answer score: 2
Revisions (0)
No revisions yet.