Welcome to MathOverflow

Question

1

Is complement of LL(k) grammar context free?

edited Jun 1 at 21:05

François G. Dorais♦
22.7k●2●48●113

asked Jun 1 at 15:03

Alex
11●1

	What is LL(k)?? – Benjamin Steinberg Jun 1 at 15:04
	en.wikipedia.org/wiki/LL_parser – Sridhar Ramesh Jun 1 at 21:30

Chris Pressey · Answer 1 · 2012-11-29 11:03:05Z UTC

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."

Is complement of LL(k) grammar context free?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.