Is complement of LL(k) grammar context free?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ What is LL(k)?? $\endgroup$– Benjamin SteinbergCommented Jun 1, 2012 at 15:04
-
1$\begingroup$ en.wikipedia.org/wiki/LL_parser $\endgroup$– Sridhar RameshCommented Jun 1, 2012 at 21:30
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
In general, the complement of a context-free language is not context-free. However, LL(k) languages are a strict subset of the deterministic CFLs.
The complement of a DCFL is also a DCFL, because it can be recognized by the same deterministic push-down automaton, just with the "accept" and "reject" states swapped.
So the answer to your question appears to be "yes, in fact it is deterministic context-free."
