search
Log In
1 vote
85 views

If L1 and L2 are non-regular, then L⋃ L2 is also non-regular.

state the above statement is true or false?

in Theory of Computation
edited by
85 views
3
False..

L1=a^nb^m | n=m

L2=a^nb^m| n not equal to m

Both are CFL

But their union gives a*b* which is regular.

1 Answer

0 votes
let L1= a^m b^n m,n>=1 m>=n   non regular

let l2=a^m b^n m,n>=1 m<n non regular

union l3= a^m b^n m,n>=1 m>=n or m<n}

equivalent to{ a^m b^n m,n>=1 } is regular

Related questions

0 votes
0 answers
1
93 views
Let A be a regular set. Consider the two sets below L1={x | $\exists n\geq 0, \exists y\epsilon A :$ y=$x^n$} L2={x | $\exists n\geq 0, \exists y\epsilon A :$ x=$y^n$} which of the following statements is true? L1 and L2 both are regular L1 is regular but L2 is not L1 is not regular but L2 is L1 and L2 both are non-regular
asked Mar 17, 2019 in Theory of Computation aditi19 93 views
2 votes
1 answer
2
152 views
Consider the infinite two-dimensional grid $G=\{(m,n)|\text{m and n are integers} \}$ Thus every point in G has 4 neighbours, North, South, East and West, obtained by varying m or n by $\pm 1$. Starting at origin (0,0), a string of command letters N, S, E, W generates a path in G. For ... $L'$ is context free A. 1,2 and 3 only B. 3 and 4 only C. 4 only D. 1 and 2 only
asked Mar 2, 2018 in Theory of Computation GateAspirant999 152 views
0 votes
0 answers
3
160 views
Why is the answer D? How to solve it in simple way other than learning Rice Theorem? Does anyone know Rice thm in short?
asked Jan 12, 2017 in Theory of Computation Purple 160 views
...