The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+3 votes
258 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
in Theory of Computation by Active (3.4k points)
edited by | 258 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

@srestha 

$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.:)

2 Answers

+1 vote
Best answer

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

by Boss (34.9k 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+ ?
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.
by (87 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,339 questions
55,765 answers
192,355 comments
90,815 users