Scribd
Upload
12 views14 pages

DFA Design for Binary Languages

The document contains exercises related to designing Deterministic Finite Automata (DFA) for various binary and alphabetic languages. It includes tasks such as creating state diagrams, answering questions about given DFAs, and constructing DFAs for specific language properties. The exercises cover a range of topics including acceptance conditions, state transitions, and language intersections and complements.

Uploaded by

هزّاع سعيد
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
12 views14 pages

DFA Design for Binary Languages

The document contains exercises related to designing Deterministic Finite Automata (DFA) for various binary and alphabetic languages. It includes tasks such as creating state diagrams, answering questions about given DFAs, and constructing DFAs for specific language properties. The exercises cover a range of topics including acceptance conditions, state transitions, and language intersections and complements.

Uploaded by

هزّاع سعيد
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

CHAPTER 1

REGULAR LANGUAGES
Q1
Design a DFA that accepts all binary strings that either
have an odd number of 1’s or end in a 1
Q2
1.1 The following are the state diagrams of two DFAs, M1 and M2. Answer
the following questions about each of these machines.

a. What is the start state?


b. What is the set of accept states?
c. What sequence of states does the machine go through on input aabb?
d. Does the machine accept the string aabb?
e. Does the machine accept the string ε?
Q3
1.2 Give the formal description of the machines M1 and
M2 pictured in Exercise 1.1.
Q4
1.3 The formal description of a DFA M is ({q1, q2, q3, q4,
q5}, {u, d}, δ, q3, {q3}), where δ is given by the
following table. Give the state diagram of this machine.
Q5
1.6 Give state diagrams of DFAs recognizing the following
languages. In all parts, the alphabet is {0,1}.

a. {w| w begins with a 1 and ends with a 0}


Q6
1.6 Give state diagrams of DFAs recognizing the following
languages. In all parts, the alphabet is {0,1}.

b. {w| w contains at least three 1s}


Q7
1.6 Give state diagrams of DFAs recognizing the following
languages. In all parts, the alphabet is {0,1}.

e. {w| w starts with 0 and has odd length, or starts with 1 and
has even length}
Q8
1.6 Give state diagrams of DFAs recognizing the following
languages. In all parts, the alphabet is {0,1}.

k. {ε, 0}
Q9
1.6 Give state diagrams of DFAs recognizing the following
languages. In all parts, the alphabet is {0,1}.

i. {w| every odd position of w is a 1}


Q10
1.4 Each of the following languages is the intersection of
two simpler languages. In each part, construct DFAs for
the simpler languages, then combine them using the
construction discussed in footnote 3 (page 46) to give the
state diagram of a DFA for the language given. In all
parts, Σ = {a, b}

a. {w| w has at least three a’s and at least two b’s}


Q11
1.4 Each of the following languages is the intersection of
two simpler languages. In each part, construct DFAs for
the simpler languages, then combine them using the
construction discussed in footnote 3 (page 46) to give the
state diagram of a DFA for the language given. In all
parts, Σ = {a, b}

c. {w| w has an even number of a’s and one or two


b’s}
Q12
1.5 Each of the following languages is the complement of
a simpler language. In each part, construct a DFA for the
simpler language, then use it to give the state diagram of
a DFA for the language given. In all parts, Σ = {a, b}

a. {w| w does not contain the substring ab}


Q13
1.5 Each of the following languages is the complement of
a simpler language. In each part, construct a DFA for the
simpler language, then use it to give the state diagram of
a DFA for the language given. In all parts, Σ = {a, b}

c. {w| w contains neither the substrings ab nor ba}

You might also like