Languages

Question

Consider a language over Σ={a,b} the description of L is given below.

L={ PQ | P ∈(a,b)* , Q ∈ (a,b)* and n_a(P) = n_b(Q) }.

 

Select the correct option.

 

1. L is DCFL but not regular.

2. L is CSL but not CFL.

3. L is CFL but not DCFL.

4. None of these.

 

 

Comments

(D) 

Language will be (a+b)* i.e. Regular langauge.

---

Yes correct

Answer 1

Language accepted by this (a+b)* only i.e REGULAR.....as we can break any string on this language in P and Q and also satisfy the condn of no. of a in P=no. of b in Q....for example abaabbaaababab here we can make P as abaabb and Q as aaababab....and here number of a in P=number of b in Q ..

Comments

Suppose if I take a string as aabbbb and let here P is aab and Q is bbb, then how will you check that the number of a in P is not equal to number of b in Q without stack?

---

i.e the thing you dnn need to check...checking would have come in picture when some of string in (a+b)* could not be accepted but in this case every string in(a+b)* can be break down in P and Q where the condn given will always be satisfied.

---

I can agree with you if in the question only it is written P belongs to (a,b)* and Q belongs to (a,b)*, So we dont need to check anything since whatever string we will take it will definately accept . But then , what is the use of writing this condition as well " number of a in P is equal to number of b in Q" . Are you not considering this condition?

---

condition will always be true for any string in this language..!

If there would have some strings for which condn did not met than we would have needed a stack but here no such case..as every string in this language gets accepted.!

Answer 2

The given language is regular language (a+b)*

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------

You may think that $n_{a}(P) = n_{b}(Q)$ requires comparison and for comparing them we need stack and stack +FA = PDA.

so it is not regular.

But here the thing is

We adjust the input string according to our requirement and divide them according to the need of the question such that

$n_{a}(P) = n_{b}(Q)$ condition satisfies.

---------------------------------------------------------------------------------------------------------------------------------------------------------------------

For eg :-

1. aabbab is the input string.

    we can divide the string like P = aab and Q = bab.

    => $n_{a}(P) = n_{b}(Q)$ = 2.

 

2. aaa is the input string.

    we can divide the string like P = $\epsilon$ and Q = aaa.

    => $n_{a}(P) = n_{b}(Q)$ = 0.

Comments

No its regular language as you can see that the P ∈(a,b)* , Q ∈ (a,b)* .

---

Yes it should be regular

---

If it would be regular  then a finite automata should exist for it.

In finite automata how will we check no. of p = no. of q ?

---

@satbir yes comaprison could not be done by finite automata but here you should see one thing the language accepted by this is (a+b)* only...you can write any string in this language and that would be accepted by this as becz P and Q could be any string on (a+b)*...for example if you take string as ababbbaabbaabb here we can say P is (ababbbaa) and Q is (bbaabb) so you can see here.... no. of a in P= no. of b in Q...so here you can string on (a+b)* no matter what they would be accepted as you can break them in P and Q strings accordingly...

---

How string 'a' or 'b' is accepted......what will be P and Q in this case....???

---

For 'a'

P = $\epsilon$ and Q = a.

=> $n_{a}(P) = n_{b}(Q)$ = 0.

--------------------------------------------

For 'b'

P = b and Q = $\epsilon$

=> $n_{a}(P) = n_{b}(Q)$ = 0.