0
$\begingroup$

I tried some examples and found that LL(1) grammar always exist.

I tried searching for formal proof but didn't find any.

Can someone give a formal proof for the above statement?

$\endgroup$
  • 4
    $\begingroup$ Have you tried proving it yourself? You need to construct a grammar from a deterministic finite automaton. $\endgroup$ – adrianN Oct 6 '17 at 15:51
  • $\begingroup$ Use the characterisation with FIRST and FOLLOW sets. $\endgroup$ – Raphael Oct 6 '17 at 23:11
  • $\begingroup$ Express the corresponding DFA as a grammar. Each state becomes a non-terminal. The transitions from a state become a production. Terminal states disjoin the empty state. $\endgroup$ – Thumbnail Oct 7 '17 at 10:24
  • $\begingroup$ Use a left-regular or a right-regular grammar. $\endgroup$ – Yuval Filmus Oct 7 '17 at 10:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.