$L=(\{ca^nb^n | n \geq 0\} \cup \{a^nb^{2n } | n \geq 0\})^*$ is not dcfl. Why?

Question

$L=(\{ca^nb^n | n \geq 0\} \cup \{a^nb^{2n } | n \geq 0\})^*$ is not dcfl. Why?

[dcfl - deterministic context free language, cfl - context free language]

How to analyse this? i am not able to vizualise pda for this? if it is kleane closure of L then i need to loop that L machine between initial and final states right? If it is union then because of dilemma between 2 transition path, we get npda. But both union and kleane closure combined, how to vizualise?

Answer 1

After rereading the question this language is actually a DCFL

We can prove this by constructing a DPDA

first lets describe how the DPDA will work and get an intuition about why it is a DPDA

DPDA works as follows :

1. if no further input accept
2. if we read c , then test for caⁿbⁿ , if the string fails reject , else return to 1
3. if we read a , then test for aⁿb²ⁿ , if the strings fails reject , else return to 1

The DPDA works as follows , first since we use * we accept the empty string , if we have an input , we observe the first string , if we read c , then we know we must read a substring caⁿbⁿ , if we read a then we know we must read a substring aⁿb²ⁿ , either way we test to see if the input we read matches the substring it should , if not reject , if it matches then we return to accept state , waiting for either an a or c to check again or for the end of input so we accept

Each step in our description follows the other deterministically with no guessing , this should give us a strong basis for our claim that L is a DCFL

Now lets formalise what we stated , to prove L is DCFL we need to provide a DPDA , this DPDA needs to :

1. follow the formal description of a DPDA , so we know for sure it is a DPDA
2. accept the language L

First here is the formal description of a DPDA :

The distinguishing part from a PDA is the restrictions imposed on the transition function

Now we provide the DPDA to recognise L:

We can see how the DPDA follows the formal description provided , the transitions from each state follow the description of the transition function in the formal description of the DPDA

We can also see that the DPDA recognises L , as it follows the procedures explained above