The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+1 vote

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

L={ PQ | P ∈(a,b)* , Q ∈ (a,b)* and na(P) = nb(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.



asked in Theory of Computation by (317 points) | 120 views


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

Yes correct

2 Answers

+1 vote
Language accepted by this (a+b)* only i.e 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 ..
answered by Active (3.9k points)
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 every string in this language gets accepted.!
0 votes

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.

answered by Active (4.9k points)
edited ago by
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)* 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 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.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
47,894 questions
52,261 answers
67,679 users