The GATE Grind

GATE 2018 CS – Question 62

Theory of Computation · Regular Expressions and Finite Automata · 2 marks · Numerical answer

Given a language $L$, define $L^i$ as follows: $L^0=\{\varepsilon\}$ and $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 automaton in the figure.

The order of $L_1$ is ________.

Diagram for GATE 2018 CS question 62

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 2

Explanation

The automaton accepts the empty string and every string of an odd number of 0's, so
$$L_1=\{\varepsilon\}\cup\{0^{2k+1}\mid k\ge0\}.$$

Compute the powers:
- $L_1^0=\{\varepsilon\}$.
- $L_1^1=L_1$: the empty string and odd lengths. The string $00\notin L_1$.
- $L_1^2=L_1\cdot L_1$: odd + odd gives every even length $\ge2$, and $\varepsilon$ + odd gives every odd length. So $L_1^2$ contains $\varepsilon$ and all $0^n$: $L_1^2=0^*$.
- $L_1^3=L_1^2\cdot L_1=0^*\cdot L_1=0^*$.

$L_1^0\ne L_1^1$ and $L_1^1\ne L_1^2$, but $L_1^2=L_1^3$. The smallest $k$ with $L^k=L^{k+1}$ is $k=\mathbf{2}$.

More Regular Expressions and Finite Automata questions

All Regular Expressions and Finite Automata questions →