Is it possible, that intersection of regular language and context-free unambiguous language is inherently ambiguous? If it is possible, give me any example please. Otherwise, I am looking for proof.
2026-03-28 07:51:46.1774684306
Is it possible, that intersection of regular language and context-free unambiguous language is inherently ambiguous?
177 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
No I think that is not possible, but you have to do a little work yourself.
If $L$ has a context-free grammar $G$, then the standard construction for a grammar for $L\cap R$ has nonterminals $[A,p,q]$ where $A$ is a nonterminal for $G$ and $p,q$ represents a path in an automaton for $R$, thus making guesses as what would be a fitting path for the derived terminal string. Now if the automaton for $R$ is deterministic and $G$ itself is unambiguous can there be several derivations for the same string?