TOC Sample practice

Question

$L1 = \{a^m b^nc^{max(m,n)} : m,n > 1\}$ $L2 = \{a^{2^n}, n > 1\} \cup \{a^m, m>1\}$

(a) Both are regular     (b) Only L2 is regular
(c) Only L1 is regular   (d) None of the above
Solution: Option (b)

how? here as l2 is not in ap it should not be regular right?

Answer 1

Here L1 is not regular

if we talk about L2=CSL U REG =REG

donot take wrong approach  CSL U REG=CSL U CSL =CSL

so L2 is regular

Comments

$L=a^{n}b^{n}c^{n}$ is CSL

$M=\phi$ is regular

$L_{U}=a^{n}b^{n}c^{n} \cup \phi=a^{n}b^{n}c^{n}$ is CSL

---

how can you say CSL U Regular = Regular ?? I am not getting it

Answer 2

 L2 is clearly a regular language because {a^m ,m>1} = (a)⁺  and it already contains every possible string generated by a^2^n.

Comments

when we union 2 DFA how and what to consider excatly? i am not getting with this union Questions

---

it is not union of 2 dfa's as {a2n,n>1} is csl  and {am,m>1} is regular.

the concept here is that 1st part is subset of 2nd part language.Hence no need to worry about 1st. part.

Answer 3

L1= {a^m b^n c^max(m,n) |m,n>1} is not regular as clearly we can see, we need comparison.

L2= {a^{2^n},n>1} ∪ {a^m,m>1}

Lets see it individually

{a^{2^n},n>1} = {a^{2^2} ,a^{2^3,} a^{2^4}.......... } {which is not regular because its not in AP(Arithmetic progression) }

{a^m,m>1} =  {aa,aaa,aaaa,..............} {this is regular language, whose regular expression is (aa+)}

{a^{2^n},n>1} ∪ {a^m,m>1} = {aa,aaa,aaaa,..............} which is regular

Answer 4

a^2^n is not regular,but we can say that a^2^n is the proper subset of a^m|m>1 so when we do union of both then all strings of a^2^n eventually becomes part of a^m|m>1.Thus it becomes regular.