edited by
9,167 views
25 votes
25 votes

Which one of the following is TRUE?

  1. The language $L = \left\{a^nb^n \mid n \geq 0\right\}$ is regular.
  2. The language $L = \left\{a^n \mid n \text{ is prime }\right\}$ is regular.
  3. The language $L$= $\left\{ w \mid w \text{ has } 3k+1 \text{ } b's \text{ for some } k\in  N \text{ with } \Sigma=\left\{ a,b \right\}\right\}$ is regular.
  4. The language $L = \left\{ww \mid w \in \Sigma^*    \text{ with } \Sigma = \left\{0,1\right\}\right\}$ is regular.
edited by

3 Answers

Best answer
34 votes
34 votes

(A) is CFL and (B) and (D) are CSL.

(C) is regular and regular expression for (C) would be: $$a^*b(a^*ba^*ba^*b)^+a^*$$

Correct Answer: $C$

edited by
4 votes
4 votes

(A) L = {a n b n |n >= 0} is not regular because there does not exists a finite automaton that can derive this grammar. Intuitively, finite automaton has finite memory, hence it can’t track number of as. It is a standard CFL though. (B) L = {a n b n |n is prime} is again not regular because there is no way to remember/check if current n is prime or not. Hence, no finite automaton exists to derive this grammar, thus it is not regular. (C) L = {w|w has 3k+1 bs} is a regular language because k is a fixed constant and we can easily emulate L as a ∗ ba ∗ .....ba ∗ such that there are exactly 3k + 1 bs and a ∗ s surrounding each b in the grammar.v_24(D) L = {ww| w ∈ Σ ∗ } is again not a regular grammar, infact it is not even a CFG. There is no way to remember and derive double word using finite automaton. Hence, correct answer would be (C). 

Answer:

Related questions

13 votes
13 votes
5 answers
1