Peter Linz Exercise 4.3

Question

Comments

for (a),i guess,we can write regular expression as (a+b)⁺ aa (a+b)⁺  + (a+b)⁺ bb (a+b)⁺

for (b),as it involves comparixson btw u and v,so it is not regular.

please correct me

---

Yes Akriti, you are right. Thanks

---

welcome :)

---

 @Akriti mam ,please extend concept little bit more means how r u writing regular expressions if (1) directly.

please explain in words..

Answer 1

1) $ L = \{ uww^{R}v : u,v,w \in \{a + b \}^{+} \} $

This is a regular language, If you look closely then you will see that we can stretch $u$ and $v$ such that we can get $w w^{R} $ as $aa$ or $bb$. 

Associated Regular expression can be : $ (a + b)^{+} . a a . (a + b)^{+} + (a + b)^{+} . b b . (a + b)^{+} $

2) $ L = \{ uww^{R}v : u,v,w \in \{a + b \}^{+}, |u| >= |v| \} $

This is not a regular language, because you need a counter to check that if $ |u| >= |v| $ ? 

Hence this is not regular.

Comments

wow beautiful :)

---

Then u are saying that

WW^r is regular --> starting and ending with same symbol (regular expression)

but actually it is not

---

Actually u and v should be extended and in center u'll gell aa or bb

See Akriti answer in comment

---

Thanks for pointing it :)

Answer 2

A) The language is regular as the input string can be broken in 4 parts where W and W^R are the same symbol, either a or b and U can be anything before W and V can be anything after W^R . The language can be defined as any string  of length 4 or more containing either aa or bb (Not at end or beginning). 

B) Same as above but there is one more constraint that |U| >= |V|, as DFA has finite memory this language cannot be Regular.