retagged by
2,242 views
12 votes
12 votes

Consider following languages :

L1 = { wxwy | x,w,y $\in$(a + b)+ } ,

L= { xwyw | x,w,y $\in$(a + b)} ,

L= { wxyw | x, y, w $\in$(a+b)

How can we say that L, Lare regular but not L? Please explain.

retagged by

1 Answer

Best answer
20 votes
20 votes

$L_1= \left\{ wxwy \;|\; x,w,y \in (a+b)^+ \right \}$

here $x,y \in(a+b)^+$ means any string having length $\geq 1$ ,( and not a big problem). 

$w$ must be same at both place having length $\geq 1$ , start with $a$ or $b$ 

$ \overbrace{a(something)}^{w}\;x\;\overbrace{a\underbrace{(something)}_{ must\; be \; same \;as \; earlier}}^w\;y + \overbrace{b(something)}^{w}\;x\;\overbrace{b\underbrace{(something)}_{ must\; be \; same \;as \; earlier}}^w\;y$

Remember $x$ and $y$ can be anything having length $\geq 1$ , i.e, belong to $(a+b)^+$, we are flexible with the length of $x$ and $y$ , except $0$ length .

$ a\;\overbrace{(something)x}^{\in (a+b)^+}\;a\; \overbrace{(something)y}^{\in (a+b)^+} + \;b\;\overbrace{(something)x}^{\in (a+b)^+}\;b\; \overbrace{(something)y}^{\in (a+b)^+}$

here if something is not same, we can say that something is part of $x$ and $y$ respectively and $w$ is simple $a$ or $b$, rest is $x$ and $y$.

$  a(a+b)^+a(a+b)^+ + b(a+b)^+b(a+b)^+$

In simple words , here $x$ and $y$ can absorb rest of the strings 

$L_1$ is Regular. 

$L_2= \left\{ xwyw \;|\; x,w,y \in (a+b)^+ \right \}$

$w$ must be same at both place having length $\geq 1$ , end with $a$ or $b$ 

$ x\;\overbrace{(something)a}^{w}\;y\;\overbrace{\underbrace{(something)}_{ must\; be \; same \;as \; earlier}a}^w + \;x\;\overbrace{(something)b}^{w}\;y\;\overbrace{\underbrace{(something)}_{ must\; be \; same \;as \; earlier}b}^w$

$ \overbrace{x(something)}^{\in (a+b)^+}\;a\; \overbrace{y(something)}^{\in (a+b)^+}\;a + \overbrace{x(something)}^{\in (a+b)^+}\;b\; \overbrace{y(something)}^{\in (a+b)^+}\;b$

 

here if something is not same, we can say that something is part of $x$ and $y$ respectively and $w$ is simple $a$ or $b$, rest is $x$ and $y$.

$ (a+b)^+a(a+b)^+a + (a+b)^+b(a+b)^+b $

In simple words , here $x$ and $y$ can absorb rest of the strings 

$L_2$ is Regular. 

 

$L_3= \left\{ wxyw \;|\; x,w,y \in (a+b)^+ \right \}$

$w$ must be same at both place having length $\geq 1$ , start with $a$ or $b$ 

 

$ \overbrace{a(something)}^{w}\;x\;y\;\overbrace{a\underbrace{(something)}_{ must\; be \; same \;as \; earlier}}^w + \overbrace{b(something)}^{w}\;x\;y\;\overbrace{b\underbrace{(something)}_{ must\; be \; same \;as \; earlier}}^w$

 

 

$ a\;\overbrace{(something)x}^{\in(a+b)^+}\;y\;a\;\overbrace{\underbrace{(something)}_{ must\; be \; same \;as \; earlier}}^{ Problem} +b\;\overbrace{(something)x}^{\in(a+b)^+}\;y\;b\overbrace{\underbrace{(something)}_{ must\; be \; same \;as \; earlier}}^{ Problem}$

 

Problem is that, there is  $x$ in right of first something , if both did not same we can say ,that can be part of $x$, but there is no $x$ or $y$ in left/right of second something, to absorb that. ( and there is $a$ or $b$ , that must be remain unchanged.)

$L_3$ is not regular. 

selected by

Related questions

0 votes
0 votes
1 answer
1
srestha asked May 24, 2018
786 views
Is it regular?$\left \{ \left ( 0^{n} \right )^{m}|n<m,n,m\geq 1 \right \}$
1 votes
1 votes
1 answer
4
Gate Mm asked Dec 8, 2015
2,618 views
L1 = {ambn | m+n = Even} L2 = {ambn | m-n = 4}(a) L1 is Regular, L2 is Not Regular(b) Both are Regular(c) Both are Non- Regular(d) L2 is Regular, L1 is Not Regular