A$.$ Design two finite automata in transition graph form that recognize strings of languages with alphabet $\{0,1\}$ and the following case$-$by$-$case constraints:

$1.$ The sequences $001$ and $111$ occur exactly twice each $($not necessarily

in a separate sequence of digits$),$ e$.$g$.$ the strings $1001001111,001011100111,$

$11100100101110$ are recognized, while e$,11101000111,00100111110$ are rejected.

$2.$ The value of the $($unsigned$)$ binary number formed by the sequence symbol $–$ as it is read from left to right $–$ is either a multiple of $3$ or

multiple of $4,$ e$.$g$.$ the strings $0100,110,10010$ are recognized, while $$epsi $,0,$

$1100,11101$ are rejected.

B$.$ For each of the finite automata, if it is non$-$deterministic, convert it to deterministic.

C$.$ Minimize the two deterministic finite automata you found.

 

Answer rating: 100% (QA)

Finite Automata for Language Constraints A Designing the Automata 11 Two Occurrences of Specific Substrings This case requires an automaton that recog... View the full answer