Both

The Gateway to Computer Science Excellence

+3 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?

- $S_1$ only
- $S_2$ only
- Both
- Neither of the above

0

Regular exp--

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

$S_2=a^+ b^+$

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

$S_2=a^+ b^+$

+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.

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.

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

0

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

and if the first question is

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

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

+1 vote

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,645 questions

56,567 answers

195,748 comments

101,704 users