Deck 12: Regular Expressions and Finite State Automata

Question 1

(a) Find the quotient automaton for A.
(b) Find the quotient automaton for
(c) Are A and
equivalent? Explain.

Answer 1

A 18

Question 2

Consider the regular expression
(a) Describe the language defined by this expression.
(b) Design a finite-state automaton to accept the language defined by the expression.

Answer 2

Question 3

Consider the finite-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:
(c) Describe the language accepted by this automaton.
(d) Find a regular expression that defines the same language.

Answer 3

Question 4

Question 5

Consider the finite-state automaton given by the following transition diagram:

Question 6

Question 7

Question 8

Question 9

Question 10

Consider the finite-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:
(c) Describe the language accepted by the automaton.
(d) Find a regular expression that defines the same language.

Question 11

Consider the finite-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:
(c) Describe the language accepted by the automaton.
(d) Find a regular expression that defines the same language.

Question 12

Consider the finite-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:
(c) Describe the language accepted by the automaton.
(d) Find a regular expression that defines the same language.

Question 13

Consider the regular expression
(a) Describe the language defined by this expression.
(b) Design a finite-state automaton to accept the language defined by the expression.

Question 14