619 views
2 votes
2 votes
L1=$\left \{ a^nb^k|n\neq k \right \} and \;L2=\left \{xyx^r|x,y\in \left \{ 0,1 \right \}^+ \right \}$

check whether the language given below is dcfl or not?

L=$\left \{ x^r|x\in L1 \;but \;not\; L2 \right \}$

1 Answer

Best answer
1 votes
1 votes

Answer : DCFL


Case 1 : If the Question has No Typo and is to be answered for what it is given. 

i.e. $L_1 = \left \{ a^nb^k|n \neq k; n,k \geq 0 \right \}$ Which is DCFL.

and $L_2 = \left \{ xyx^R| x,y \in \left \{ 0,1 \right \}^+, \,\,\,and\,\,\, w^R \,\,\,stands\,\,\, for \,\,\,reversal\,\,\, of\,\,\, string\,\,\, w. \right \}$ Which is Regular and the Regular expression is $0(0+1)^+0 + 1(0+1)^+1.$

$L = \left \{ x^R| x \in L_1\,\,\, but\,\,\, not\,\,\, in\,\,\, L_2 ; and\,\,\, w^R \,\,\,stands\,\,\, for \,\,\,reversal\,\,\, of\,\,\, string\,\,\, w.\right \}$

Since $L_1, L_2 $ are defined over different Alphabets, there is No common string between them and so Set $L$ is nothing but Reversal of language $L_1.$ So, 

$L = L_1^R = \left \{ b^ka^n|n \neq k; n,k \geq 0 \right \}$ , Which is DCFL as we know it. 


Case 2 : If the Question has Typo and $L_2$ is defined over the same alphabet as $L_1$ i.e. 

$L_1 = \left \{ a^nb^k|n \neq k; n,k \geq 0 \right \}$ Which is DCFL.

and $L_2 = \left \{ xyx^R| x,y \in \left \{ a,b \right \}^+, \,\,\,and\,\,\, w^R \,\,\,stands\,\,\, for \,\,\,reversal\,\,\, of\,\,\, string\,\,\, w. \right \}$ Which is Regular and the Regular expression is $a(a+b)^+a + b(a+b)^+b.$

$L = \left \{ x^R| x \in L_1\,\,\, but\,\,\, not\,\,\, in\,\,\, L_2 ; and\,\,\, w^R \,\,\,stands\,\,\, for \,\,\,reversal\,\,\, of\,\,\, string\,\,\, w.\right \}$

Now, If we look at $L_1,$ we can partition $L_1$ into the following languages : $a^+ , b^+, \left \{ a^nb^k|n \neq k; n,k \geq 1 \right \}$

Now, the Strings that are in $L_1$ But Not in $L_2$ are : $a,aa,b,bb, \left \{ a^nb^k|n \neq k; n,k \geq 1 \right \}$

So, $L$ is nothing but the Set of reversal of these strings i.e. 

$L = \left \{ a,aa,b,bb \right \} \cup \left \{ b^ka^n|n \neq k; n,k \geq 1 \right \}$.. Which is DCFL as we know it. ($\left \{ b^ka^n|n \neq k; n,k \geq 1 \right \}$ is DCFL and we are adding finite number of strings to it which won't affect its language type.)

selected by

Related questions

255
views
1 answers
0 votes
Vignesh859 asked May 13
255 views
How a^i b^j | i !=(2j+1) is dcfl?
211
views
1 answers
0 votes
prasoon054 asked Dec 7, 2023
211 views
Is countable sets part of GATE CS 2024 syllabus?
423
views
2 answers
3 votes
Jiten008 asked Oct 24, 2023
423 views
Can anyone explain $\overline{ww}$ is $CFL$ or $CSL$ And if $CFL$ can you write the equivalent $CFG$ for this ?
316
views
1 answers
1 votes
Swarnava Bose asked Aug 26, 2023
316 views
If L= { a^p | where p is any prime number }, then what is:- i) L+ ii) L*iii)L^3