search
Log In
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.
in Theory of Computation
recategorized by
401 views

2 Answers

0 votes
 
Best answer
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 by
0 votes
(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 answer
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.
asked Jul 4, 2017 in Theory of Computation kavikeve 1.1k views
1 vote
0 answers
2
254 views
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}$
asked Oct 4, 2016 in Theory of Computation makhdoom ghaya 254 views
1 vote
0 answers
3
333 views
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^{*}$
asked Oct 4, 2016 in Theory of Computation makhdoom ghaya 333 views
4 votes
2 answers
4
1.3k views
Consider the following identities for regular expressions : (a) (r + s)* = (s + r)* (b) (r*)* = r* (c) (r* s*)* = (r + s)* Which of the above identities are true ? (a) and (b) only (b) and (c) only (c) and (a) only (a), (b) and (c)
asked Oct 1, 2016 in Theory of Computation makhdoom ghaya 1.3k views
...