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

Objective Session 3

Let L = L1∩ L...

Question

Let L = $L_{1} \cap L_{2}$ , where $L_{1} a n d L_{2}$ are languages as defined below:
$L_{1}$ ={ $a^{m} b^{m} c a^{n} b^{n} | m, n \geq 0$ }
$L_{2}$ ={ $a^{i} b^{j} c^{k} | i, j, k \geq 0$ }
Then L is

Open in App

Solution

$L_{1}$ ={ $a^{m} b^{m} c a^{n} b^{n} | m, n \geq 0$ }
$L_{2}$ ={ $a^{i} b^{j} c^{k} | i, j, k \geq 0$ }
L = $L_{1} \cap L_{2}$
$L_{1}$ is CFL. $L_{2}$ is regular. First use closure property to get a estimate.
$L = L_{1} \cap L_{2} = C F L \cap R e g = C F L$
However,since one of the opetion (b) is regular is stronger than CFL answer obtained by closure property, we need to find the actual intersection.Any string belonging to both must have equal number of a's & b's followed by a single followed by no a's or b's; which is the only string allowed by both $L_{1}$ and $L_{2}$ .
i.e. L= $L_{1} \cap L_{2}$ ={ $a^{m} b^{m} c$ }
Now this is clearly context free, but not regular

Suggest Corrections

Similar questions

L_{1} and L 2

L_{1}

L_{2}

D C F L .

L_{3} = (L_{1} \cap L_{2}^{*})^{'}

L_{3}

L_{1} = 0^{*} 1^{*}, L_{2} = 1^{*} 0^{*}, L_{3} = (0 + 1)^{*} and L_{4} = 0^{*} 1^{*} 0^{*} .

L = (L_{1} \cap L_{2}) - (L_{3} \cap L_{4})

L_{1} a n d L_{2}

L_{1} \cdot L_{2}

" \cdot "

L_{1} = {a^{n} | n \geq 0}

L_{2} = {b^{n} | n \geq 0}

L_{1} = {a^{n} ∣ n \geq 0}

L_{2} = {b^{n} ∣ n \geq 0}

L_{1} \cdot L_{2}

L_{1} \cdot L_{2} = {a^{n} b^{n} ∣ n \geq 0}

L e t L_{1} =

0^{n + m} 1^{n} 0^{m} | n, m \geq 0

L_{2} =

0^{n + m} 1^{n + m} 0^{m} | n, m \geq 0

L_{3} =

0^{n + m} 1^{n + m} 0^{n + m} | n, m \geq 0

Join BYJU'S Learning Program