Question 1

Finite-state automata $A$ and $A ^ { \prime }$ are defined by the transition diagrams shown below.

(a) Find the quotient automaton for A.
(b) Find the quotient automaton for$A ^ { \prime }$ 
(c) Are A and $A ^ { \prime }$  equivalent? Explain.

Accepted Answer

a. For $A$ :
the 0 -equivalence classes are $\left\{ s _ { 0 } , s _ { 1 } , s _ { 2 } , s _ { 3 } , s _ { 5 } \right\} , \left\{ s _ { 4 } , s _ { 6 } \right\}$.
the 1-equivalence classes are $\left\{ s _ { 0 } , s _ { 1 } , s _ { 5 } \right\} , \left\{ s _ { 2 } , s _ { 3 } \right\} , \left\{ s _ { 4 } , s _ { 6 } \right\}$.
the 2 -equivalence classes are $\left\{ s _ { 0 } , s _ { 1 } \right\} , \left\{ s _ { 5 } \right\} , \left\{ s _ { 2 } , s _ { 3 } \right\} , \left\{ s _ { 4 } , s _ { 6 } \right\}$.
the $*$-equivalence classes are $\left\{ s _ { 0 } , s _ { 1 } \right\} , \left\{ s _ { 5 } \right\} , \left\{ s _ { 2 } , s _ { 3 } \right\} , \left\{ s _ { 4 } , s _ { 6 } \right\}$.
The quotient automaton for $A , \bar { A }$, has the following transition diagram:

A b. For $A ^ { \prime }$ :
the 0 -equivalence classes are $\left\{ s _ { 0 } ^ { \prime } , s _ { 1 } ^ { \prime } , s _ { 3 } ^ { \prime } , s _ { 4 } ^ { \prime } \right\} , \left\{ s _ { 2 } ^ { \prime } \right\}$.
the 1 -equivalence classes are $\left\{ s _ { 0 } ^ { \prime } , s _ { 3 } ^ { \prime } , s _ { 4 } ^ { \prime } \right\} , \left\{ s _ { 1 } ^ { \prime } \right\} , \left\{ s _ { 2 } ^ { \prime } \right\}$.
the 2-equivalence classes are $\left\{ s _ { 0 } ^ { \prime } \right\} , \left\{ s _ { 1 } ^ { \prime } \right\} , \left\{ s _ { 3 } ^ { \prime } , s _ { 4 } ^ { \prime } \right\} \left\{ s _ { 2 } ^ { \prime } \right\}$.
the $*$-equivalence classes are $\left\{ s _ { 0 } ^ { \prime } \right\} , \left\{ s _ { 1 } ^ { \prime } \right\} , \left\{ s _ { 3 } ^ { \prime } , s _ { 4 } ^ { \prime } \right\} \left\{ s _ { 2 } ^ { \prime } \right\}$.
The quotient automaton for $A ^ { \prime } , \overline { A ^ { \prime } }$, has the following transition diagram:  c. The transition diagrams for $\bar { A }$ and $\overline { A ^ { \prime } }$ are identical except for the names of the states. Thus both accept the same language, and since $A$ accepts the same language as $\bar { A }$ and $A ^ { \prime }$ accepts the same language as $\overline { A ^ { \prime } } , A$ and $A ^ { \prime }$ accept the same language. Hence they are equivalent automata.

Question 2

Consider the regular expression $$0 ^ { * } 10 ^ { * } \mid 0 ^ { * } 10 ^ { * } 10 ^ { * }$$ 
(a) Describe the language deﬁned by this expression.
(b) Design a ﬁnite-state automaton to accept the language deﬁned by the expression.

Accepted Answer

a. The language accepted by the automaton is the set of all strings of 0 's and 1 's that contain exactly one 1 or that contain exactly two 1 's.
b.

Question 3

Consider the ﬁnite-state automaton given by the following next-state table:  
(a) Draw the transition diagram for the automaton.
(b) Indicate which of the following strings are accepted by the automaton: $$\begin{array} { l l l l } 
0100 & 101 & 1110 & 00101
\end{array}$$ 
(c) Describe the language accepted by this automaton.
(d) Find a regular expression that deﬁnes the same language.

Accepted Answer

a.

b. The strings 101 and 1110 are accepted by the automaton. The strings 0100 and 00101 are not accepted by the automaton.
c. The language accepted by the automaton is the set of all strings of 0's and 1's that start with a 1 and contain at least one more $1 .$
d. $10 ^ { * } 1 ( 0 \mid 1 ) ^ { * }$

Question 4

Consider the language that consists of all strings of 0 's and 1's in which the number of 1's is evenly divisible by 4 . Find a regular expression that defines this language.

Accepted Answer

The answer of Consider the language that consists of all...

Question 5

Consider the ﬁnite-state automaton given by the following transition diagram:  
 (a) What is $N \left( s _ { 2 } , a \right)$ ?
(b) To what state does the automaton go if the string babaa is input to it?
(c) Indicate which of the following strings are accepted by the automaton: $$a b a b \quad b b a b \quad a b b b a a \quad a$$
(d) Describe the language accepted by this automaton.
(e) Find a regular expression that defines the same language.

Accepted Answer

The answer of Consider the ﬁnite-state automaton given by the...

Question 6

Consider the language that consists of all strings of $a$ 's and $b$ 's in which the second character from the beginning is a $b$. Find a regular expression that defines this language.

Accepted Answer

The answer of Consider the language that consists of all...

Question 7

Let $L$ be the language defined by the regular expression $( x \mid y ) ^ { * } x ( x \mid y )$.
(a) Write 3 strings that belong to $L$
(b) Use words to describe $L$.

Accepted Answer

The answer of Let $L$ be the language defined by...

Question 8

Let $\Sigma = \{ 0,1 \}$, and let $L$ be the language over $\Sigma$ consisting of all strings of 0 's and 1 's of length 4 with an equal number of 0 's and 1's. List the elements of $L$.

Accepted Answer

The answer of Let $\Sigma = \{ 0,1 \}$, and...

Question 9

Prove that there is no finite-state automaton that accepts the language $L$ consisting of all strings of $x$ 's and $y$ 's of the form $x ^ { n } y ^ { n }$ where $n$ is a positive integer.

Accepted Answer

The answer of Prove that there is no finite-state automaton...

Question 10

Consider the ﬁnite-state automaton given by the following next-state table:  
(a) Draw the transition diagram for this automaton.
(b) Indicate which of the following strings are accepted by the automaton: $$\begin{array} { l l l l } 
0100 & 1001 & 0110 & 101010
\end{array}$$ 
(c) Describe the language accepted by the automaton.
(d) Find a regular expression that deﬁnes the same language.

Accepted Answer

The answer of Consider the ﬁnite-state automaton given by the...

Question 11

Consider the ﬁnite-state automaton given by the following next-state table:  
(a) Draw the transition diagram for this automaton.
(b) Indicate which of the following strings are accepted by the automaton: $$\text { abba babb ba bbababa }$$ 
(c) Describe the language accepted by the automaton.
(d) Find a regular expression that deﬁnes the same language.

Accepted Answer

The answer of Consider the ﬁnite-state automaton given by the...

Question 12

Consider the ﬁnite-state automaton given by the following transition diagram:  
(a) To what state does the automaton go if the string 10010010 is input to it? Is this string accepted by the automaton?
(b) Indicate which of the following strings are accepted by the automaton: $$\begin{array} { l l l l } 
000101 & 0100010 & 000100 & 110001
\end{array}$$ 
(c) Describe the language accepted by the automaton.
(d) Find a regular expression that deﬁnes the same language.

Accepted Answer

The answer of Consider the ﬁnite-state automaton given by the...

Question 13

Consider the regular expression $a ( a \mid b ) ^ { * } b$
(a) Describe the language deﬁned by this expression.
(b) Design a ﬁnite-state automaton to accept the language deﬁned by the expression.

Accepted Answer

The answer of Consider the regular expression \(a ( a...

Question 14

Let $L$ be the language defined by the regular expression $0 ( 0 \mid 1 ) ^ { * } 1 ( 0 \mid 1 ) ^ { * }$.
(a) Write 3 strings that belong to $L$
(b) Use words to describe $L$.

Accepted Answer

The answer of Let $L$ be the language defined by...

Quiz 12: Regular Expressions and Finite State Automata

Consider the regular expression $0 ^ { * } 10 ^ { * } \mid 0 ^ { * } 10 ^ { * } 10 ^ { * }$ (a) Describe the language deﬁned by this expression. (b) Design a ﬁnite-state automaton to accept the language deﬁned by the expression.

Consider the language that consists of all strings of 0 's and 1's in which the number of 1's is evenly divisible by 4 . Find a regular expression that defines this language.

Consider the language that consists of all strings of $a$ 's and $b$ 's in which the second character from the beginning is a $b$ . Find a regular expression that defines this language.

Let $L$ be the language defined by the regular expression $( x \mid y ) ^ { * } x ( x \mid y )$ . (a) Write 3 strings that belong to $L$ (b) Use words to describe $L$ .

Let $\Sigma = \{ 0,1 \}$ , and let $L$ be the language over $\Sigma$ consisting of all strings of 0 's and 1 's of length 4 with an equal number of 0 's and 1's. List the elements of $L$ .

Prove that there is no finite-state automaton that accepts the language $L$ consisting of all strings of $x$ 's and $y$ 's of the form $x ^ { n } y ^ { n }$ where $n$ is a positive integer.

Consider the regular expression $a ( a \mid b ) ^ { * } b$ (a) Describe the language deﬁned by this expression. (b) Design a ﬁnite-state automaton to accept the language deﬁned by the expression.

Let $L$ be the language defined by the regular expression $0 ( 0 \mid 1 ) ^ { * } 1 ( 0 \mid 1 ) ^ { * }$ . (a) Write 3 strings that belong to $L$ (b) Use words to describe $L$ .

Quiz 12: Regular Expressions and Finite State Automata

Finite-state automata AAA and A′A ^ { \prime }A′ are defined by the transition diagrams shown below. (a) Find the quotient automaton for A. (b) Find the quotient automaton for A′A ^ { \prime }A′ (c) Are A and A′A ^ { \prime }A′ equivalent? Explain.

Consider the regular expression 0∗10∗∣0∗10∗10∗0 ^ { * } 10 ^ { * } \mid 0 ^ { * } 10 ^ { * } 10 ^ { * }0∗10∗∣0∗10∗10∗ (a) Describe the language deﬁned by this expression. (b) Design a ﬁnite-state automaton to accept the language deﬁned by the expression.

Consider the language that consists of all strings of 0 's and 1's in which the number of 1's is evenly divisible by 4 . Find a regular expression that defines this language.

Consider the language that consists of all strings of aaa 's and bbb 's in which the second character from the beginning is a bbb . Find a regular expression that defines this language.

Let LLL be the language defined by the regular expression (x∣y)∗x(x∣y)( x \mid y ) ^ { * } x ( x \mid y )(x∣y)∗x(x∣y) . (a) Write 3 strings that belong to LLL (b) Use words to describe LLL .

Let Σ={0,1}\Sigma = \{ 0,1 \}Σ={0,1} , and let LLL be the language over Σ\SigmaΣ consisting of all strings of 0 's and 1 's of length 4 with an equal number of 0 's and 1's. List the elements of LLL .

Prove that there is no finite-state automaton that accepts the language LLL consisting of all strings of xxx 's and yyy 's of the form xnynx ^ { n } y ^ { n }xnyn where nnn is a positive integer.

Consider the regular expression a(a∣b)∗ba ( a \mid b ) ^ { * } ba(a∣b)∗b (a) Describe the language deﬁned by this expression. (b) Design a ﬁnite-state automaton to accept the language deﬁned by the expression.

Let LLL be the language defined by the regular expression 0(0∣1)∗1(0∣1)∗0 ( 0 \mid 1 ) ^ { * } 1 ( 0 \mid 1 ) ^ { * }0(0∣1)∗1(0∣1)∗ . (a) Write 3 strings that belong to LLL (b) Use words to describe LLL .

Consider the regular expression $0 ^ { * } 10 ^ { * } \mid 0 ^ { * } 10 ^ { * } 10 ^ { * }$ (a) Describe the language deﬁned by this expression. (b) Design a ﬁnite-state automaton to accept the language deﬁned by the expression.

Consider the language that consists of all strings of $a$ 's and $b$ 's in which the second character from the beginning is a $b$ . Find a regular expression that defines this language.

Let $L$ be the language defined by the regular expression $( x \mid y ) ^ { * } x ( x \mid y )$ . (a) Write 3 strings that belong to $L$ (b) Use words to describe $L$ .

Let $\Sigma = \{ 0,1 \}$ , and let $L$ be the language over $\Sigma$ consisting of all strings of 0 's and 1 's of length 4 with an equal number of 0 's and 1's. List the elements of $L$ .

Prove that there is no finite-state automaton that accepts the language $L$ consisting of all strings of $x$ 's and $y$ 's of the form $x ^ { n } y ^ { n }$ where $n$ is a positive integer.

Consider the regular expression $a ( a \mid b ) ^ { * } b$ (a) Describe the language deﬁned by this expression. (b) Design a ﬁnite-state automaton to accept the language deﬁned by the expression.

Let $L$ be the language defined by the regular expression $0 ( 0 \mid 1 ) ^ { * } 1 ( 0 \mid 1 ) ^ { * }$ . (a) Write 3 strings that belong to $L$ (b) Use words to describe $L$ .