regular language

Question

which of the following is regular grammar?

a) L1 = { XcY | X,Y belongs to (a,b)* and c is constant }.

b) L2 = { WcW^r | W belongs to (a,b)* and W^r is the reverse of W }.

 

Please answer with explanation.

Comments

option 1 only ?

---

L₁ = (a+b)^*c(a+b)^*  // Regular , easily NFA can be drawn

L₂ : DCFL , not regular as to match strings Stack needed ...here by the help of c , PDA will have a clear idea when to POP so it's deterministic => DCFL

Answer 1

Option 1 only as L₁ can be written as (a+b)*c(a+b)* // any string containing c as a sub-string.

For L₁ F.A can be drawn easily therefore L₁ is regular.

L₂  is not regular as F.A cannot compare W and W^r , It can be easily done by deterministic PDA (For occurrence of W i.e. (a+b)* in the string push into stack until first c is seen and after that match the input with top of the stack and POP if matched). Therefore L₂ is DCFL.