2,510 views
0 votes
0 votes
Let $Σ = \{a, b\}.$ For each $k\geq 1,$ let $C_{k}$ be the language consisting of all strings that contain an a exactly $k$ places from the right-hand end$.$ Thus $C_{k}=\sum^{*}a\sum^{k-1}.$ Describe an $\text{NFA}$ with $k + 1$ states that recognizes $C_{k}$ in terms of both a state diagram and a formal description$.$

1 Answer

0 votes
0 votes

$C_{1}$=(a+b)*a

$C_{2}$=(a+b)*a(a+b)

$C_{3}$=(a+b)*a(a+b)(a+b)

$C_{k}$=(a+b)*a(a+b)........(a+b) [there are k-1 (a+b) terms appended after a]

Formal description=$M(Q, \sum, \delta, q0, F)$

Q={q0, q1,.........., qk}

$\sum$={a, b}

q0=initial state

F={qk}

transition: $\delta$(q0, b)=q0, 

                   $\delta$(q0, a)=q0, $\delta$(q0, a)=q1

                   $\delta$(i-1, b)=qi, $\delta$(i-1, a)=qi for $2\leq i\leq k$

Related questions