Given a language πΏ, define πΏπ as follows: πΏ0 = {π} πΏπ = πΏπβ1 β πΏβ¦
2018
Given a language πΏ, define πΏπ as follows:
πΏ0 = {π}
πΏπΒ = πΏπβ1 β πΏ πππ πππ π > 0
The order of a languageΒ πΏ is defined as the smallestΒ \(k\) such that πΏπ = πΏπ+1 .
Consider the language πΏ1 (over alphabet 0) accepted by the following automaton.
The order of πΏ1 is _____.
Attempted by 109 students.
Show answer & explanation
Correct answer: 2
Answer: 2
Explanation:
From the automaton: the start state is accepting, and after one 0 you reach another accepting state. Further 0s alternate between an accepting and a non-accepting state. So the language L consists of the empty string and all nonempty strings of odd length: L = {Ξ΅} βͺ {0(00)*}.
Compute powers:
β’ L^0 = {Ξ΅}.
β’ L^1 = L = {Ξ΅} βͺ odd-length strings of 0s.
β’ L^2 = L β L. Looking at lengths: {0} βͺ odd plus itself gives every nonnegative integer (0 = 0+0, any odd = odd+0, any even β₯2 = odd+odd). So L^2 = 0* (all strings of 0s).
β’ Once we have L^2 = 0*, further concatenation with L leaves 0* unchanged, so L^3 = L^2.
Therefore the smallest k with L^k = L^{k+1} is k = 2.