Consider the following languages over the alphabet -0-1-c-L1 -0n 1n -n- 0L2 -wcwr - w -0-1-L3 -wwr - w -0-1-Here-wr is the reverse of the string w- Which of these languages are deterministic Context-free languages-

L_1 =0^n 1^n |n≥ 0 is DCFL L_2 =wcw^r | w ϵ0,1* is DCFL L_3 =ww^r | w ϵ0,1* is CFL but nbsp; not nbsp; nbsp;DCFL ...

You visited us 1 times! Enjoying our articles? Unlock Full Access!

Objective Session 3

Consider the ...

Question

Consider the following languages over the alphabet $\sum$ ={0,1,c};
$L_{1}$ ={ $0^{n} 1^{n} | n \geq 0$ }
$L_{2}$ ={ $w c w^{r} | w ϵ$ {0,1}}
$L_{3}$ ={ $w w^{r} | w ϵ$ {0,1}}
Here, $w^{r}$ is the reverse of the string w. Which of these languages are deterministic Context-free languages?

None of the languages

No worries! We‘ve got your back. Try BYJU‘S free classes today!

Only

L_{1}

and

L_{2}

Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses

Only

L_{1}

No worries! We‘ve got your back. Try BYJU‘S free classes today!

All the three languages

No worries! We‘ve got your back. Try BYJU‘S free classes today!

Open in App

Solution

Suggest Corrections

Similar questions

L_{1} : {(X Y)^{m} x^{m} y^{m} | m > 0}

L_{2} : {X^{*} Y^{*} Z^{*} {X^{m} Y^{m} Z^{m} | m > 0}}

L_{3} : {(w ϵ {0, 1}^{*} | \exists K \geq 0 and w is a binary encoding of K)}

L = {w ϵ {0, 1}^{*} ∣ w e n d s w i t h t h e s u b s t r i n g 0110}

w^{R}

w^{R}

L_{1} = {0^{m} 1^{n} ∣ 0 \leq m \leq n \leq 10000}

L_{2} = {w ∣ w r e a d s t h e s a m e f r o w a r d a n d b a c k w a r d}

L_{3} = {w ϵ {0, 1}^{*} ∣ w c o n t a i n s a n e v e n n u m b e r o f 0^{'} s a n d a n e v e n n u m b e r o f 1^{'} s}

L_{1} : {w x w^{R} ∣ w, x ϵ {a, b}^{*} a n d ∣ w ∣, ∣ x ∣> 0}

w^{R}

L_{2} : {a^{n} b^{m} ∣ m \neq n a n d m, n \geq 0}

L_{3} : {a^{p} b^{q} c^{r} ∣ p, q, r \geq 0}

Join BYJU'S Learning Program