MadeEasy Test Series: Theory Of Computation - Regular Languages

Question

Consider the following statements:

$S_1:\{(a^n)^m|n\leq m\geq0\}$

$S_2:\{a^nb^n|n\geq 1\} \cup \{a^nb^m|n \geq1,m \geq 1\} $

Which of the following is regular?

1. $S_1$ only
2. $S_2$ only
3. Both
4. Neither of the above

Comments

$a$ and $b$ dependent here.

So, cannot be regular.:)

---

Option C , both are regular.

---

https://gateoverflow.in/261354/madeeasy-test-series-theory-computation-regular-languages

Answer 1

We can drow a dfa for s1 and s2 .so both are regular.

Comments

S2 : {a^nb^n | n>=1} U {a^nb^m | n>=1, m>=1}
S2 : DCFL U REGULAR
S2 : DCFL

Is it correct ?

---

yes correct, but more likely,it will be regular

as it is $a^{*}b^{*}$

---

S2 is a*b* or a+b+ ?

Answer 2

$ ((a)^{n})^{m} $ can be rewritten as $ ((a)^{1})^{nm} $

Actually the reasoning should be the other way around $ (a)^{k} = (a^{1})^{k} = (a^{1})^{mn} = L ~ ~\forall k \in \mathbb{N} $

This language is obviously regular.

Language 2 is the union of L1 and L2 where L1 $\subset$ L2 and L2 is regular. Hence L1 $\cup$ L2=L2, which is regular.

Comments

@Joey

S2 is not a union of 2 Regular languages.

{a^nb^n |n>=1} is not regular

---

Yeah, sorry about that.

Answer 3

option C

becuase
L1={ epsilon , a,a2,a3 ,a3 ,a4...............}where all are in power of a means  L1=a* so it is regular.


L={a1b1∪a2b1∪a3b1∪.......∪a2b2........∞} so L2=a^nb^m so it is also regular.