GATE 2014 CS (CS1) – Question 25

Theory of Computation · Regular and Context-Free Languages, Pumping Lemma · 1 mark · Multiple choice

Which one of the following is TRUE?

$L=\{a^nb^n:n\ge0\}$ is regular.
$L=\{a^n:n\text{ is prime}\}$ is regular.
$L=\{w:w\text{ has }3k+1\text{ b symbols for some }k\in\mathbb N,\ \Sigma=\{a,b\}\}$ is regular.
$L=\{ww:w\in\Sigma^*,\ \Sigma=\{0,1\}\}$ is regular.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $L=\{w:w\text{ has }3k+1\text{ b symbols for some }k\in\mathbb N,\ \Sigma=\{a,b\}\}$ is regular.

Explanation

A finite automaton can count the b symbols modulo 3 and ignore the a symbols. Accepting residue 1 recognises exactly the strings with $3k+1$ b symbols, so **C** is regular.

The other three need unbounded memory (equal numbers of a and b, unary prime lengths, an unrestricted repeated half) and are not regular.