DCFL

Question

Is DFCL closed under complement ? If so can you provide any text for the same.

Answer 1

DCFL are closed under compliment.

Firstly, what do we mean by deterministic CFL?
It means we can make a Deterministic Push Down Machine which accepts this language.

Now, What do we mean by a Deterministic PDA?
It means at any state, we won't have a choice. This is because in a deterministic machine, there are no epsilon moves possible and there will only be unique moves possible for a given symbol. In a nutshell, for a given state and symbol, we can "determine" the next state of the machine without any ambiguity.

Now, to get the complement of DPDA, all you have to do is to toggle the final and non-final states of the PDA. If you do so, your PDA will still stay deterministic. Hence, DCFL are closed under compliment.

Comments

read this https://cs.stackexchange.com/questions/18800/demonstrate-that-dpda-is-closed-under-complement-by-construction/23171

---

"there are no epsilon moves possible."

There are epsilon moves possible but there should not be any transition which consumes any input for same top of stack, if there is epsilon move defined in dpda.

---

@sushmita madam can you explain the above statement with the help of example

Answer 2

DCFL's are closed under complement

because LANGUAGE L= {a^mb^m/m>=1} is DCFL and  its complement( ∑*-L) is also DCFL

Comments

Okay got it ...thank you :)

---

its ok

---

I have a doubt pls, how to draw the dfa for ∑*-L?

Thanks