913 views
1 votes
1 votes

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.

 

 

2 Answers

1 votes
1 votes
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 votes
0 votes

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


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

$\rightarrow$ so it is not regular.

$\rightarrow$ But here the thing is

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

$\rightarrow$ $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.

edited by

Related questions

2 votes
2 votes
2 answers
2
No_name asked Apr 7, 2017
2,377 views
I need two proves, i am stuckhere1.Show that every S-grammar is Unambiguous2.Show that a RegEx can never be Inherently Ambiguousso what to use here? Induction/Contradicti...
1 votes
1 votes
0 answers
4
Sambhrant Maurya asked Oct 14, 2018
335 views
Let r1 = (b*ab*ab*ab*)* and r2= (b*ab*ab*)*. What is L(r1) ∩ L(r2)?a) L[b*ab*ab*ab*)*]b) L[b*ab*ab*)*]c) L[b*ab*ab*)6]d) L[b*ab*ab*ab*ab*ab*ab*)*]