91Ó°ÊÓ

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

Each grammar in Exercises is proposed as generating the set \(L\) of strings over \(\\{a, b\\}\) that contain equal numbers of a's and b's. If the grammar generates \(L\), prove that it does so. If the grammar does not generate \(L\), give a counterexample and prove that your counterexample is correct. In each grammar, \(S\) is the starting symbol. $$ S \rightarrow a B|b A| \lambda, B \rightarrow b|b A, A \rightarrow a| a B $$

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 nondeterministic finite-state automata that accept the strings over \(\\{a, b\\}\) having the properties specified. Having each \(b\) preceded and followed by an \(a\)

Each grammar in Exercises is proposed as generating the set \(L\) of strings over \(\\{a, b\\}\) that contain equal numbers of a's and b's. If the grammar generates \(L\), prove that it does so. If the grammar does not generate \(L\), give a counterexample and prove that your counterexample is correct. In each grammar, \(S\) is the starting symbol. $$ S \rightarrow a S b|b S a| S S \mid \lambda $$

Design nondeterministic finite-state automata that accept the strings over \(\\{a, b\\}\) having the properties specified. Starting with \(a b\) but not ending with \(a b\)

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

Show that there is no finite-state machine that receives a bit string and outputs 1 whenever the number of 1's input equals the number of 0 's input and outputs 0 otherwise.

Design nondeterministic finite-state automata that accept the strings over \(\\{a, b\\}\) having the properties specified. Not containing \(b a\) or \(b b b\)

Prove or disprove: If \(L\) is a regular language, so is $$\left\\{u^{n} \mid u \in L, n \in\\{1,2, \ldots\\}\right\\}$$