The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
84 views

Let L be a given context-free language over the alphabet {a, b}. Construct L1, L2 as follows.
Let L1 = L − {xyx | x, y ∈ {a, b}},
and L2 = L·L. Then,

(A) Both L1 and L2 are regular.

B) Both L1 and L2 are context free but not necessarily regular.

(C) L1 is regular and L2 is context free.

(D) L1 and L2 both may not be context free 

closed as a duplicate of: Virtual GATE Question
asked in Theory of Computation by Loyal (8.4k points)
closed by | 84 views
0
L1 = $CFL - REG$

= $CFL \cap \overline {REG} $

= $CFL \cap REG$

= $CFL$

L2 = CFL concat CFL = CFL

So according to me b).

Where am I wrong?
0
option C
0
tuhin here L is regular...sigma *
0
ok, I understood. Thanks bro
0
How is L1 regular? L is context free and the language being subtracted is regular.CFL -Regular is regular, right?
0
how xyx is regular as we have to store x such that it comes again after y?Please correct me if I am wrong
0
I got Tuhin's derivation but I am not able to understand what was wrong in it. Please elaborate :)
0
how you are saying that xyx is regular?
0
you have a string

Let the first and last symbol be x

rest as y

Now, the problem is reduced to strings starting with same or different symbol. Which is regular.
0
Thanks bro. I confused (a,b)* with ∈*
+1
@Gaurav, L is REG and CFL too which I took as only CFL and that is where I got it wrong.
0
If a language is cfl then how you can say that it is reular too?
0

Check out the Chomsky hierarchy, you'll get to know.

0
Bro if a language is regular you can say that it is cfl but converse is not true. a^nb^n is cfl but not regular
0
That is exactly, what has been told in the question.
0
So if by that logic if L is regular because it is CFL isn't L.L(concatenation) also regular and hence L1 and L2 both regular ? I am still not getting how L1 is regular and L2 is CFL (I got the L2 is CFL part)
0
you can take L as (a+b)* and xyx can be written as (a+b)*, so difference will be phi and that is regular.

and in case of L2 cfl.cfl is cfl
0
Given L is CFL and (a+b)* is not CFL.

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,263 questions
49,758 answers
164,197 comments
65,849 users