whether the following languages are DCFL or not???

Question

$$L_1 = \left \{a^n \,c\, b^n \right \} \cup \left \{ a^{2n} \,d\, b^n \right \}$$
$$L_2 = \left \{a^{3k} \, b^{3k} \mid k \geq 0 \right \}$$

Answer 1

Both are dcfl, we have dpda for them

1. Read 2 $a's$ and push 1 $a$, we have have of $a's$ on stack

Now If we get $c$, it means we have double count of $b's$ than those of $a's$ on stack. So on reading two $b$ pop one $a$ ( means do nothing for one $b$, pop one $a$ with one $b$) 

​Or, if we get $d$, it means we have same number of $b's$, those of $a's$. So pop one $a$ on reading one $b$. 

​Given $c$ or $d$,  make clear what to do, it is deterministic. 

2. is also dcfl, push one $a$ on reading 3 $a$, pop one $a$ on reading 3 $b's$. 

Comments

There may be different logic for 1 also. 

Push all a's, if get c, pop one a with one b, if get d, then pop 2 a with one b. 

But c/d make it clear deterministic. 

---

sir,for 1 st figure from q3 to q4 why after reading b as input,it is keeping a as it is,it shoul pop a,means instead of (b,a,a) it should be (b,a,^)..pls correct me sir,if i am wrong

---

Actually, we pushed half of a's in stack so after reading c, we have b's in double count of a's.  So on reading 2 b, pop one a. So q3 to q4 is do nothing, q4 to q5 pop one a,  and repeat the process.

---

Sir,here epsilon violates prefix property of DCFL?

---

@praveen Saini

​​​​​​Both of them are dcfl's. But the second pda you've drawn has a null move and a true input move defined for the state q0 when the stack top is z0. This makes it a non deterministic PDA.

q0,€,z0 and q0,a,z0

Here's how to make it a dpda. Modify q0 to be the start and final state to accept null. Redirect all accepting configurations to q0. Do all the counting on other states.

 

Hope you correct this.

---

@Praveen Saini Sir, in 2nd Question, in (qo,a,z0) -----> (q1, az0)

Sir, why are we pushing a on TOS in qo as you said, we will push one "a" after reading 3a's

---

in next two, we have DONOTHING moves

---

@Praveen Saini Sir, can't we have DONOTHING in first two ie (qo to q1) and (q0 to q2) and then in (q2 to q3) in this transition we push "a" like (a,zo/az0)

Also, will you please explain what's happening on (q3 to q1) the (a,a/aa) why are we pushing a's again? For 6,9,12 a's?

---

1. you can push at any one out of 3 transitions

2. from q3 to q1, we are repeating same process, 1 push(q3 to q1) , 2 donothing (q1 to q3)

---

@Praveen Saini Sir, is this PDA correct, I'm pushing "a" at (q2 to q3)

in order to zoom the image - https://gateoverflow.in/?qa=blob&qa_blobid=10899362868043996052

---

No, q0 to q1 .. DONOTHING for first a (first time), q1 to q2.. DONOTHING for second a (first time), q2 to q3 .. Push a (first time), q3..to q1 ..wrong here (correct.. DONOTHING first a (a,a,a) ), ...q1 to q2...wrong here (correct.. DONOTHING second a ( add transition using comma (a,a,a) ).... q2 to q3..wrong here..(correct.. Push a .(add transition using comma (a,a,aa))..

Answer 2

1.Union of 2CFL will be NCFL

It is a NCFL

2.DCFL

Comments

thank you sir for clear explanation

---

Sorry My Bad, this is wrong way to solve this, because we're not able to give DFA becuase a's and b's are not same and if you try to make DFA, it will accept strings which are not in L like "aaabbbbbb".

Hence L2 is not RL, Thanks Arjun Sir.

In, L2={ a^3kb^3k ∣k≥0}

L = { e, aaabbb, aaaaaaabbbbbb, aaaaaaaaabbbbbbbbb.........}

e ----> when k=0

aaabbb ------> when k=1, string length is "6"

aaaaaabbbbbb ------> when k=2, string length is "12"

aaaaaaaaabbbbbbbbb -------> when k=3, string length is "18"

.

.

Now, if you may see, the common difference is 6. Hence we can say this L is in AP and hence it's regular and hence DCFL?

---

What is this "AP" thing? If you say $L_2$ is regular, you can give a DFA for it.