**(D)**

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

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+1 vote

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.

+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 ..

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 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.

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 ?

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...

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 556
- Exam Queries 551
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,894 questions

52,261 answers

182,169 comments

67,679 users