GATE CSE 2014 Set 1 | Question: 15

Question

Which one of the following is TRUE?

• A. The language $L = \left\{a^nb^n \mid n \geq 0\right\}$ is regular.
• B. The language $L = \left\{a^n \mid n \text{ is prime }\right\}$ is regular.
• C. 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.
• D. The language $L = \left\{ww \mid w \in \Sigma^*    \text{ with } \Sigma = \left\{0,1\right\}\right\}$ is regular.

Answer 1

(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$

Comments

Note :K value belongs to natural number .So minimum number of b must be 4

---

In the option, K belongs to a Natural Number set. Thus, the numbers of b accepted must be at least 4. This DFA accepts 1 b also.

---

@अनुराग पाण्डेय Your diagram is wrong. k belongs to set of natural numbers which do not contain 0 , so you need to increase the number of states to 7 i guess.

Answer 2

so the option c is correct.

Answer 3

(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.(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).