if df has 2 states and one of the state is initial and final then it would accept empty string too which is not part of the language as n>=1 if incase n>=o then it would be regular

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+12 votes

Consider the following two statements:

$S_1: \left\{ 0^{2n} \mid n \geq 1 \right\}$ is a regular language

$S_2: \left\{0^m1^n0^{m+n} \mid m \geq 1 \text{ and } n \geq 1 \right\}$ is a regular language

Which of the following statement is correct?

- Only $S_1$ is correct
- Only $S_2$ is correct
- Both $S_1$ and $S_2$ are correct
- None of $S_1$ and $S_2$ is correct

+15 votes

Best answer

Only $S_1$ is correct!

A DFA with $3$ states will be needed, as the strings in the language $S_1$ are $00, 0000, 000000,$ and so on. which is the set of all strings with even number of $0's$ and with length greater than $0$. We would have needed only $2$ sates had empty string also been in the language but $n\geq 1$ prohibits it and so we need $3$ states in our DFA. This assumes that the language is over $\{0\}$ and not $\{0,1\}.$

$S_2$ is DCFL as we need to do infinite counting of $0's$ and $1's$ here.

A DFA with $3$ states will be needed, as the strings in the language $S_1$ are $00, 0000, 000000,$ and so on. which is the set of all strings with even number of $0's$ and with length greater than $0$. We would have needed only $2$ sates had empty string also been in the language but $n\geq 1$ prohibits it and so we need $3$ states in our DFA. This assumes that the language is over $\{0\}$ and not $\{0,1\}.$

$S_2$ is DCFL as we need to do infinite counting of $0's$ and $1's$ here.

0

i think both are false

if df has 2 states and one of the state is initial and final then it would accept empty string too which is not part of the language as n>=1 if incase n>=o then it would be regular

if df has 2 states and one of the state is initial and final then it would accept empty string too which is not part of the language as n>=1 if incase n>=o then it would be regular

0

@Bhagirathi-

Can you explain me why S2 is not regular. it is 0^2m 1^2n , we can construct regular language fr 0^ 2m and same for 1^2n and unioin them. m and n are not dependent

Can you explain me why S2 is not regular. it is 0^2m 1^2n , we can construct regular language fr 0^ 2m and same for 1^2n and unioin them. m and n are not dependent

0

@Divya Bharti

Read the question carefully

S2 is not 02m 12n

S2:{0m1n0m+n∣m≥1 and n≥1}

S2 is not regular because last 0 is dependent on value of m and n

Read the question carefully

S2 is not 02m 12n

S2:{0m1n0m+n∣m≥1 and n≥1}

S2 is not regular because last 0 is dependent on value of m and n

+12 votes

**DFA For S _{1 }:**

**S _{2} is PDA** since stack is needed for comparision finite memory is not sufficient

Till 1 push in stack after that pop from stack for every 0.

0

I have a question is S2 dcfl or not?

According to me it is

According 2 me

We can push 0 and 1 on the stack and then pop 1's and 0's

Plz do correct me if i m wrong

According to me it is

According 2 me

We can push 0 and 1 on the stack and then pop 1's and 0's

Plz do correct me if i m wrong

0

Hi @sourav ji, Thank You.

I think this answer is corrected.

If you assume you have only 0 then selected answer is correct.

In that case also, I think we can not do in 2 states. Min 3 states are required because n>=1.

+1

Chhotu $\text{both selected as well as non selected answer are correct}$

Actually the question itself is little bit unclear because set of possible input symbols are not given.

- If you assume you have only $0$ then selected answer is correct.
- If you assume you have $0,1$ then Prashant's answer is correct.

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 5k
- Digital Logic 2k
- Programming & DS 3.6k
- Algorithms 3.1k
- Theory of Computation 3.9k
- Compiler Design 1.5k
- Databases 2.9k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 1k
- Others 1.4k
- Admissions 412
- Exam Queries 419
- Tier 1 Placement Questions 17
- Job Queries 55
- Projects 9

34,942 questions

41,954 answers

119,194 comments

41,471 users