Cheap and Secure Web Hosting Provider : See Now

[Answers] Three languages and how to decide if they are regular

, , No Comments
Problem Detail: 

From following languages which one is regular and why others are not?And what is the regular expression for regular one.

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

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

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

Also where can I find these type of problems?

Asked By : user1917769

Answered By : Denis

The first two are regular, because they can be written as $aA^*aA^*+bA^*bA^*$ and $A^*aA^*a+A^*bA^*b$ (where $A=a+b$). This is because it is enough to check them for $|w|=1$, as it is implied by longer $w$.

The last language is not regular, because its intersection with the regular language $a^+b^+aba^+b^+$ is $\{a^nb^maba^nb^m| n,m\geq 1\}$ which is not regular (you can show this by pumping lemma).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37450

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback