edited by
15,104 views
24 votes
24 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?

  1. Only $S_1$ is correct
  2. Only $S_2$ is correct
  3. Both $S_1$ and $S_2$ are correct
  4. None of $S_1$ and $S_2$ is correct
edited by

2 Answers

Best answer
25 votes
25 votes

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.

edited by
15 votes
15 votes

DFA For S1 :

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

Answer:

Related questions

16.2k
views
3 answers
30 votes
Kathleen asked Sep 14, 2014
16,207 views
Given an arbitrary non-deterministic finite automaton (NFA) with $N$ states, the maximum number of states in an equivalent minimized DFA at least$N^2$2^N$2N$N!$
14.1k
views
3 answers
30 votes
Kathleen asked Sep 14, 2014
14,139 views
Which of the following statements is true?If a language is context free it can always be accepted by a deterministic push-down automatonThe union of two ... is a context freeThe complement of a context free language is a context free
8.3k
views
5 answers
21 votes
Kathleen asked Sep 14, 2014
8,346 views
Consider the following languages:$L1=\left\{ww \mid w \in \{a,b\}^*\right\}$ ... are regular?Only $L1$ and $L2$Only $L2, L3$ and $L4$Only $L3$ and $L4$Only $L3$
5.5k
views
3 answers
33 votes
Kathleen asked Sep 14, 2014
5,517 views
Let a decision problem $X$ be defined as follows:$X$: Given a Turing machine $M$ over $\Sigma$ and any word $w \in \Sigma$, does $M$ loop ... but partially decidable.Show that $X$ is undecidableShow that $X$ is not even partially decidable