282 views 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 | 282 views
0
Both
0
explain.
0
Regular exp--

$S_1={a^*}$  ( take n=1 and m>=1, epsilon can be generated by taking n=0)

$S_2=a^+ b^+$
0
but how to check the condition whether n<=m or not for S1,

doesn't it need pda?
+1
Consider a^6

Various (n,m) are (1,6),(2,3),(3,2),(6,1).

So will a^6 be accepted or not?

It will be accepted because there exist atleast one pair (n,m) such that n<=m.
0
And we can give a pair (1,m) ==> a^m   ,m>=1

It doesn't require any comparison and language accepted by (a^m+ eps) is same as S1.
0

@Verma Ashish

Okay..thank u.. :)

one more thing, say in case of S2 if we were given intersection instead of union then it wouldn't have been regular right?

+1
Yes then it will be CFL
0
okay.. :)
0

@Hirak

Try to type the question instead of posting screenshot in the above manner

0
It is clearly visible thats why done so..
+1
and if the first question is

$\left \{ \left ( a^{n} \right )^{m}.b^{n} \right \}$, then it would be NCFL or CSL??
0

$L=\{\epsilon, a^+b,(aa)^+bb,(aaa)^+bbb,\ldots\}$

i don't know how it will be NCFL or CSL..

+1

@Verma Ashish

it will be $L=\left \{ a^{1}b^{1}\cup a^{2} b^{1}\cup a^{3}b^{1}\cup .......\cup a^{2}b^{2}........\infty\right \}$

0
Yes.

$\epsilon$  also included.

But how it will be cSL or CFL?
0
$a$ and $b$ dependent here.

So, cannot be regular.:)

+1 vote

We can drow a dfa for s1 and s2 .so both are regular. by Boss (35.7k points)
selected by
0
DFA for S2 is incorrect..
0
yes 4 states are there
0
S2 : {a^nb^n | n>=1} U {a^nb^m | n>=1, m>=1}
S2 : DCFL U REGULAR
S2 : DCFL

Is it correct ?
0
yes correct, but more likely,it will be regular

as it is $a^{*}b^{*}$
0
S2 is a*b* or a+b+ ?
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.
by (87 points)