edited by
1,729 views
5 votes
5 votes

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
edited by

3 Answers

Best answer
3 votes
3 votes

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

selected by
1 votes
1 votes
$ ((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.
edited by
0 votes
0 votes
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.

Related questions

0 votes
0 votes
1 answer
1
7 votes
7 votes
4 answers
4
ARUN KUMAR 3 asked Oct 17, 2016
3,205 views
Which of the following is a non-regular language?$L = \{wxwy \mid x,y,w \in (a+b)^+\}$$L = \{xwyw \mid x,y,w \in (a+b)^+\}$$L = \{wxyw \mid x,y,w \in (a+b)^+\}$All of the...