654 views
1 votes
1 votes

L2={wwRx∣w,x∈{0,1}}

DCFL or not ?

2 Answers

1 votes
1 votes

L2={ww$^{R}$ x ∣ w,x ∈ {0,1}$^{*}$}

L2 is regular. Since, w can be ϵ and x∈(0+1)$^{*}$, making L2=(0+1)$^{*}$=Σ$^{*}$. i.e.; the set of strings generated by L2 is {ϵ,0,1,00,01,10,11,000,…}=Σ$^{*}$

Hence, L2 is also DCFL.

if asked for,

L={ww$^{R}$ x ∣ w,x∈ (0+1)$^{+}$}

Here, w cannot be ϵ and hence to accept the string we do need the power of a PDA making L,  NCFL (non-determinism is required to guess the start of W).

 

 

0 votes
0 votes
It is definitely not DCFL but obviously CFL because we have no idea when to pop up the reverse of w.

Related questions

4 votes
4 votes
2 answers
1
srestha asked Jun 22, 2018
1,624 views
$\left \{ a^{m+n}b^{m+n}c^{n}|m,n\geq 1 \right \}$$\left \{ a^{m+n}b^{m+n}c^{k} |m,n,k\geq 1\right \}$$\left \{ a^{m+n}b^{m+k}c^{n+k} |m,n,k\geq 1\right \}$Which one DCFL...
1 votes
1 votes
2 answers
2
atul_21 asked Dec 21, 2017
874 views
$L1 = \bigl\{a^mb^nc^pd^q \mid m+q = n+p \bigr\}$$L2 = \bigl\{a^mb^nc^pd^q \mid m+p = n+q \bigr\}$1. L1 is DCFL, L2 is not2. L2 is DCFL, L1 is not3. Both are not DCFL...
1 votes
1 votes
1 answer
3
pranab ray asked Dec 9, 2017
708 views
0 votes
0 votes
1 answer
4
shivangi5 asked Dec 2, 2017
880 views
Consider the following languages:L1={abna2n|n>=0}L2={aabna3n|n>=0}Why L1UL2 is DCFL please explain?