91Ó°ÊÓ

Draw the transition diagram of the nondeterministic finite-state automaton \(\left(\mathcal{I}, \mathcal{S}, f, \mathcal{A}, \sigma_{0}\right) .\) $\mathcal{I}=\\{a, b\\}, \mathcal{S}=\left\\{\sigma_{0}, \sigma_{1}, \sigma_{2}\right\\}, \mathcal{A}=\left\\{\sigma_{0}\right\\}$$$\begin{array}{l|cc}\hline \mathcal{I} & a & b \\\\\hline \sigma_{0} & \varnothing & \left\\{\sigma_{1}, \sigma_{2}\right\\} \\\\\sigma_{1} & \left\\{\sigma_{2}\right\\} & \left\\{\sigma_{0}, \sigma_{1}\right\\} \\\\\sigma_{2} & \left\\{\sigma_{0}\right\\} & \varnothing\end{array}$$

Determine whether the given grammar is contextsensitive, context-free, regular, or none of these. Give all characterizations that apply. \(T=\\{a, b, c\\}, N=\\{\sigma, A, B\\},\) with productions $$\sigma \rightarrow B A B, \quad \sigma \rightarrow A B A, \quad A \rightarrow A B$$ $$B \rightarrow B A, \quad A \rightarrow a A, \quad A \rightarrow a b$$ $$B \rightarrow b$$ and starting symbol \(\sigma\).

Write a grammar that generates the strings having the given property. All strings over \(\\{a, b\\}\)

Design a finite-state machine having the given properties. The input is always a bit string. Outputs 1 if two or more 1 's are input; otherwise, outputs 0

Draw the transition diagram of a finite-state automaton that accepts the given set of strings over \(\\{a, b\\}\). At least two \(a\) 's

Design a finite-state machine having the given properties. The input is always a bit string. Outputs 1 when it sees 101 and thereafter; otherwise, outputs 0

Draw the transition diagram of a finite-state automaton that accepts the given set of strings over \(\\{a, b\\}\). Ends with \(a b a\)

Draw the transition diagram of a finite-state automaton that accepts the given set of strings over \(\\{a, b\\}\). Starts with \(a b\) and ends with baa