GATE 2018 CS Q.52: solution and answer

GATE 2018 · CSQ.52 · 2 marks · NAT

Given a language $L$ , define $L^{i}$ as follows:
$L^{0} = {ε}$
$L^{i} = L^{i - 1} \cdot L for all i > 0$
The order of a language $L$ is defined as the smallest $k$ such that $L^{k} = L^{k + 1}$ . Consider the language $L_{1}$ (over alphabet 0) accepted by the following automaton. The order of $L_{1}$ is ______.

GATE 2018 CS question 52: State diagram with three states in a row. — Figure from the GATE 2018 CS paper. It is part of the question.

Answer and solution

ANSWER

The order of $L_{1}$ is 2.

Official answer: 2Source: Official answer key, GATE 2018 CS (IIT Guwahati)

Name the states: $q_{0}$ is the start state and is accepting, $q_{1}$ is accepting, $q_{2}$ is non-accepting. The transitions are $δ (q_{0}, 0) = q_{1}$ , $δ (q_{1}, 0) = q_{2}$ and $δ (q_{2}, 0) = q_{1}$ .
Track the state after $n$ zeros. $n = 0$ gives $q_{0}$ , $n = 1$ gives $q_{1}$ , $n = 2$ gives $q_{2}$ , $n = 3$ gives $q_{1}$ , and from then on the state alternates $q_{2}, q_{1}, \dots$ . So $q_{1}$ is reached exactly after an odd number of zeros.
Accepted strings are $ε$ (in $q_{0}$ ) and $0^{n}$ for odd $n$ . Hence $L_{1} = {ε} \cup {0^{n} ∣ n odd}$ .
$L^{0} = {ε}$ and $L^{1} = L_{1}$ , which contains $0$ . So $L^{0} \neq = L^{1}$ . Also $0^{2} \in / L_{1} = L^{1}$ , so $L^{1}$ will differ from $L^{2}$ if $0^{2} \in L^{2}$ , which is checked next.
$L^{2} = L_{1} \cdot L_{1}$ . Odd length followed by odd length gives every even length $\geq 2$ . Concatenating $ε$ with $0^{n}$ ( $n$ odd) gives the odd lengths, and $εε = ε$ gives length 0. So $L^{2} = 0^{*}$ , which contains $0^{2}$ , and so $L^{1} \neq = L^{2}$ .
$L^{3} = L^{2} \cdot L_{1} = 0^{*} \cdot L_{1}$ . Every string of this set is a power of 0, so $L^{3} \subseteq 0^{*}$ . Since $ε \in L_{1}$ , every $0^{n}$ is $0^{n} \cdot ε \in L^{3}$ . So $L^{3} = 0^{*} = L^{2}$ .
$L^{0} \neq = L^{1}$ , $L^{1} \neq = L^{2}$ and $L^{2} = L^{3}$ , so the smallest $k$ with $L^{k} = L^{k + 1}$ is $k = 2$ .

KEY IDEA

Find the language of the automaton, then compute successive powers. Because $ε \in L_{1}$ , the powers grow ( $L^{k} \subseteq L^{k + 1}$ ), and once a power equals $0^{*}$ it cannot change.

WATCH OUT FOR

Forgetting that the start state is accepting, so $ε \in L_{1}$ . Without it $L^{2}$ would miss the odd lengths and the powers would not stabilise at $2$ .

From the GATE 2018 CS paper. Every question of this paper · Download the full paper · All 18 Finite automata questions, with notes

GATE 2018 CS Q.52: solution and answer

Answer and solution

More Finite automata questions