Context Free Languages

Question

Which of the following is/are CFL?

1) L = { xy | |x|=|y| }

2) L = { x#y | |x|=|y| }

Comments

both are CFL.....

even first one is regular....L = { xy | |x|=|y| } accept all the strings of even length...

---

How is it regular?

If it accept all even length strings, then x=101 and y=10101 wont b accepted????

---

@Sumiran

x=101 and y=10101....it will be accepted..

combining xy we get 10110101, now partition in two parts as shown below,

10110101(i have reconstructed it to x=1011 and y=0101) and |x|=|y|.....so accepted

---

Ohkie. Thankew

Answer 1

Both 1 and 2 are CFL.

as both can be accepted by using push down automata.

Language 1 generates the strings of type xy ,xxyy, xxxyyy and so on which can be accepted by pushing all x into the stack and then for every y pop one x out of the stack .

Language 2 generates the strings of type x#y, xx#yy, xxx#yyy and so on which can be accepted by pushing all x into the stack after that we have to skip the # and then for every y we have to pop one x out of the stack.

In both cases the PDA accepts the string with empty stack .

Comments

Is anyone out of them regular???

---

Yes the first one. As it can generate all the strings with even length.

Mentioned in the above comments.

---

Yep yep. Thankew