Finite State Automaton for the language over $ \{0,1\}: $ $k^{th}$ last index is $1$

110 Views Asked by At

For $k\geq 1$, let $L_k$ be the Language of all binary words with a $1$ at the $k^{th}$ last position, i.e. $L_k = \{w \in \{0,1\}: w = u1a_1...a_{k-1}$ for one $u \in \{0,1\}$ and $a_j \in \{0,1\}\}$.

For a task regarding this language a subtask I am unable to solve is this: Give a Finite State Automaton for a given k with k+1 states.

(For this Automaton the Powerset Construction is supposed to have $2^{k+1}$ states)

1

There are 1 best solutions below

0
On

You need one state for counting each of the last $k-1$ symbols. The transitions are for all possible symbols along the sequence $q_1 \rightarrow q_2 \rightarrow \cdots \rightarrow q_{k-1} $. The only final state is $q_{k-1}$.

Finally there is a start state $q_0$ with loops for all the symbols and with one transition for the symbol $1$ to $q_1$ (guessing that this is the $k$ to last symbol).

These are only $k$ states. Maybe your automata are required to be complete and also have a sink state, which would make it $k+1$.

I have not verified how many states the power set construction would result in. But your language is quite ugly for deterministic machines, so the number should be in the order of $2^{k+1}$.