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

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 (245 points) | 108 views
+1

(D) 

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

2 Answers

+1 vote
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 ..
answered by Active (3.9k points)
0
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?
0
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.
0
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?
0
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.!
0 votes

Since in this number of  P = number of Q

so we have use comparison for checking it. So we can't make a Finite automata for it.

so it cant be a regular language.


 


 

answered by Junior (875 points)
edited by
0
No its regular language as you can see that the P ∈(a,b)* , Q ∈ (a,b)* .
0
Yes it should be regular
0
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 ?
0
@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...
0
How string 'a' or 'b' is accepted......what will be P and Q in this case....???

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

42,575 questions
48,564 answers
155,449 comments
63,584 users