# UGCNET-AUG2016-III: 55

1 vote
401 views

Given the following two languages :

$L_{1} = {uww^{R} ν | u, v, w \in (a, b)^{+}}$

$L_{2} = {uww^{R} ν | u, ν, w \in (a, b)^{+} , |u| \geq |ν|}$

Which of the following is correct ?

1. $L_{1}$ is regular language and $L_{2}$ is not regular language.
2. $L_{1}$ is not regular language and $L_{2}$ is regular language.
3. Both $L_{1}$ and $L_{2}$ are regular languages.
4. Both $L_{1}$ and $L_{2}$ are not regular languages.

recategorized

Option A is correct

L1 is regular B/C      u and  v can eat up all string except 2 length string one is w and wr

now the language became string contating aa or bb

L2 is not regular B/C we need stack to compare length of

|u|≥|ν|

selected
(A) is the correct option! L1 is regular while L2 is non-regular.

For L1 since ww^r is there, at some point of the string we should have either aa or bb.

while in Language L2 there is a comparison between the length of u and v which can't be done by DFA.

## Related questions

1 vote
1
1.1k views
Given the following two languages: $L_1 = \{uww^{r}ν \mid u, v, w \in \{a, b\}^+\}$ $L_2 = \{uww^{r}ν \mid u, ν, w \in \{a, b\}^+ , |u| > |ν|\}$ Which of the following is correct ? $L_1$ is regular language and $L_2$ is not regular language. $L_1$ is not regular language and $L_2$ is regular language. Both $L_1$ and $L_2$ are regular languages. Both $L_1$ and $L_2$ are not regular languages.
1 vote
Let $G = (V, T, S, P)$ be a context-free grammar such that every one of its productions is of the form $A \rightarrow ν$, with $|ν| = k > 1$. The derivation tree for any string $W \in L (G)$ has a height such that $h < \frac{(|W|-1)}{k-1}$ $\log_{k} |W| \leq h$ $\log_{k} |W| < h < \frac{(|W|-1)}{k-1}$ $\log_{k} |W| \leq h \leq \frac{(|W|-1)}{k-1}$
Given a Turing Machine $M = ({q_{0} , q_{1} }, {0, 1}, {0, 1, B}, \delta, B, {q_{1} })$ Where δ is a transition function defined as $\delta(q_{0}, 0) = (q_{0}, 0, R)$ $\delta(q_{0}, B) = (q_{1}, B, R)$ The language $L(M)$ accepted by Turing machine is given as : $0^{*} 1^{*}$ $00^{*}$ $10^{*}$ $1^{*}0^{*}$