Rewrite Systems

$($a$)$ Given the same input, i$.$e$.,$ a sequence of characters starting with $ and

ending with #$,$ and any combination of $0$s and $1$s in$-$between, specify a

set of rewrite rules that determine whether the string contains an even

number of $0$s$.$

Here is some sample $$output$$:

$$0011$# should be rewritten as $0011->$ A

$$10001$# should be rewritten as $10001->$ B

$$110110$# should be rewritten as $110110->$ A

$$0001100$# should be rewritten as $0001100->$ B

$($b$)$ Is there only one rewrite rule that can be applied at any step of your

rewrite process $($using your defined rewriting rules$)?$ Explain.

$($c$)$ Show the steps of your rewrite system for the input strings $$0101$# and

$$1000$#$.$

$2$ Regular Expressions

Write a regular expression for the following languages.

$($a$)$ All strings of a$$s$,$ b$$s$,$ and c$$s that start with cbc$.$

$($b$)$ All binary strings that contain exactly two $1$s$.$

$($c$)$ All strings of a$$s$,$ b$$s$,$ and c$$s that do not contain more than $1$ a$,2$ b$$s$,$

$1$ c$.$

$($d$)$ All strings of a$$s$,$ b$$s$,$ and c$$s with an even number of a$$s$.$

$($e$)$ Binary string with no two consecutive $1$s$.$

$($f$)$ All strings of $1$s and $0$s where the numbers alternate, for instance,

$101010,$ and $0101.$

$1$

$3$ Minimizing A DFA

See if the following DFA can be minimized. If so$,$ please draw the minimized

DFA and also specify the initial state s$,$ the final $($accept$)$ state F$,$ the state

transitions T$,$ and the set of states S$.$ If not, justify why.