self made

Question

Q1. {aⁿ bⁿ } U { aⁿ b²ⁿ } U {aⁿ b³ⁿ } U{aⁿ b⁴ⁿ} ...Is it in DCFL OR CFL?

Q2. {aⁿ} U {aⁿ bⁿ} is it in DCFL OR CFL? Please explain with solution....

Comments

Q1- CFL

Q2- DCFL

Answer 1

1. NCFL ===> Here , if a input is given then there is no chance to deterministically know that which language will operate (actually all are DCFL particularly, but DCFL are not closed under union ).Hence , all of them  will parallely operate , making their union a NCFL.

2. DCFL ===>  Count a's and increment stack. If no b comes go to final state even if stack is not empty . If b comes then decrement the stack and go to final state only if stack is empty. No, non-determinism required. Hence , DCFL .

Comments

@Kapil AS we know Infinite union of CFL is may or may not CFL.

But here language is {aⁿ bⁿ } U { aⁿ b²ⁿ } U {aⁿ b³ⁿ } U{aⁿ b⁴ⁿ}............

i think we can,t draw pda for this language .Since we don,t know how many choices are here .So it is not CFL .

But as arjun sir said we can write an algorithm for it- same as having a TM. It is after all taking an input n, and checking if the number of b's is a multiple of it.So off-course  REC.

---

@Srestha No. Linear bounded automata means the space complexity of the algorithm must be linear multiple of input length - which is the case here. So, the language is CSL. The language of most of the solvable problems we see will be CSL.

---

@Manoj, yes, once we do a match for $a^nb^n$, we can't do it for $a^nb^{2n}$. So, it is NCFL.

Answer 2

Q1)CFL but not DCFL

Q2)DCFL

Comments

For the second one, keep counting a's and increment stack. If no b comes go to final state. If b comes decrement stack and go to final state only if stack is empty. No, non-determinism required. Hence DCFL.

---

Yes You are right. Thank you So much for the explanation