Exam 13: Modeling Computation

Find a set of two productions that produces $\left\{ 1 ^ { 2 n } \mid n > 0 \right\}$

Find a production of the form $“ A \rightarrow \underline{\quad\quad}"$ such that $S \rightarrow 1 S , S \rightarrow 0 A , A \rightarrow \underline{\quad\quad}$ produces $\left\{ 1 ^ { n } 00 \mid n \geq 0 \right\}$

Suppose a phrase-structure grammar has productions $S \rightarrow S 0 , S \rightarrow A 1 , A \rightarrow 0$ Find a derivation of 01

Construct a finite-state machine with output that produces a 1 if and only if the last 3 input bits read are 0's.

Let A={1,10} . Which strings belong to A* ?

Find the language recognized by this nondeterministic finite-state automaton.

Which strings belong to the regular set represented by the regular expression $\left( \mathbf { 1 } ^ { * } \mathbf { 0 } \mathbf { 1 } ^ { * } \mathbf { 0 } \right) ?$

Construct a finite-state automaton that recognizes all strings that end with 11.

Find the language recognized by this nondeterministic finite-state automaton.

Find the Kleene closure of A = {00}.