Question

Let$\mathbf{\Sigma }\mathbf{=}\left\{a,b\right\}$ . For each $\mathbf{k}\mathbf{⩾}\mathbf{1}$, let ${\mathbf{C}}_{\mathbf{k}}$be the language consisting of all strings that contain an a exactly K places from the right-hand end.

Thus${\mathbf{C}}_{\mathbf{k}}\mathbf{=}{\mathbf{\Sigma }}^{\mathbf{*}}\mathbf{a\Sigma }{}^{\mathbf{k}\mathbf{-}\mathbf{1}}$ . Describe an NFA with $\mathit{k}\mathbf{+}\mathbf{1}$states that recognizes ${\mathbf{C}}_{\mathbf{k}}$in terms of both a state diagram and a formal description.

Short answer

A non deterministic finite automaton with$k+1$ states that recognizes$C_k$ in terms of both a state diagram and a formal description is given below.

Step-by-step solution

Non deterministic finite automata.

Context free language is a grammar where its language or string that formed by context free grammar is supports pushdown deterministic automata.InNon deterministic finite automata, for a particular input symbol, the machine can move to any combination of the states in the machine. In other words, the exact state to which the machine moves cannot be determined.

Solution.

$$\begin{gathered} C_1=\left(a+b\right)*a \\ {C}_2=\left(a+b\right)*a\left(a+b\right) \\ {C}_3=\left(a+b\right)*a\left(a+b\right)\left(a+b\right) \\ {C}_4=\left(a+b\right)*a\left(a+b\right)........\left(a+b\right)\left[therearek-1\left(a+b\right)termsappendedaftera\right] \end{gathered}$$

$$\begin{gathered} Formaldescription=M(Q,\sum ,\delta ,q_0,F) \\ Q=\left\{q_0,q_1,..........,q_k\right\} \\ \sum =\left\{a,b\right\} \\ {q}_0=initialstate \end{gathered}$$

localid="1660806669374" $$\begin{gathered} F=\left\{qk\right\} \\ Transition:\delta (q_0,b)=q_0, \\ :\delta (q_0,a)=q_0\delta (q_0,a)=1 \\ :\delta (i-1,b)=q_i,\delta (i-1,a)=qfor2⩽i⩽k \end{gathered}$$