# PDF Archive

Easily share your PDF documents with your contacts, on the Web and Social Networks.

## HW1 questions .pdf

Original filename: HW1 questions.pdf

This PDF 1.7 document has been generated by PDFium, and has been sent on pdf-archive.com on 05/09/2017 at 15:30, from IP address 138.238.x.x. The current document download page has been viewed 936 times.
File size: 104 KB (2 pages).
Privacy: public file

### Document preview

EXERCISES

83

EXERCISES
A

1.1 The following are the state diagrams of two DFAs, M1 and M2 . Answer the following questions about each of these machines.

a.
b.
c.
d.
e.
A

What is the start state?
What is the set of accept states?
What sequence of states does the machine go through on input aabb?
Does the machine accept the string aabb?
Does the machine accept the string ε?

1.2 Give the formal description of the machines M1 and M2 pictured in Exercise 1.1.

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.
q1
q2
q3
q4
q5

u
q1
q1
q2
q3
q4

d
q2
q3
q4
q5
q5

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.
b.
c.
A
d.
e.
f.
g.

A

{w| w has at least three a’s and at least two b’s}
{w| w has exactly two a’s and at least two b’s}
{w| w has an even number of a’s and one or two b’s}
{w| w has an even number of a’s and each a is followed by at least one b}
{w| w starts with an a and has at most one b}
{w| w has an odd number of a’s and ends with a b}
{w| w has even length and an odd number of a’s}

Copyright 2013 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from
the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to
remove additional content at any time if subsequent rights restrictions require it.

84

CHAPTER 1 / REGULAR LANGUAGES

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
A

a.
b.
c.
d.
e.
f.
g.
h.

{w| w does not contain the substring ab}
{w| w does not contain the substring baba}
{w| w contains neither the substrings ab nor ba}
{w| w is any string not in a∗ b∗ }
{w| w is any string not in (ab+ )∗ }
{w| w is any string not in a∗ ∪ b∗ }
{w| w is any string that doesn’t contain exactly two a’s}
{w| w is any string except a and b}

1.6 Give state diagrams of DFAs recognizing the following languages. In all parts, the
alphabet is {0,1}.
a.
b.
c.
d.
e.
f.
g.
h.
i.
j.
k.
l.
m.
n.

{w| w begins with a 1 and ends with a 0}
{w| w contains at least three 1s}
{w| w contains the substring 0101 (i.e., w = x0101y for some x and y)}
{w| w has length at least 3 and its third symbol is a 0}
{w| w starts with 0 and has odd length, or starts with 1 and has even length}
{w| w doesn’t contain the substring 110}
{w| the length of w is at most 5}
{w| w is any string except 11 and 111}
{w| every odd position of w is a 1}
{w| w contains at least two 0s and at most one 1}
{ε, 0}
{w| w contains an even number of 0s, or contains exactly two 1s}
The empty set
All strings except the empty string

1.7 Give state diagrams of NFAs with the specified number of states recognizing each
of the following languages. In all parts, the alphabet is {0,1}.
A

a.
b.
c.
d.
e.
A
f.
g.
h.

The language {w| w ends with 00} with three states
The language of Exercise 1.6c with five states
The language of Exercise 1.6l with six states
The language {0} with two states
The language 0∗ 1∗ 0+ with three states
The language 1∗ (001+ )∗ with three states
The language {ε} with one state
The language 0∗ with one state

1.8 Use the construction in the proof of Theorem 1.45 to give the state diagrams of
NFAs recognizing the union of the languages described in
a. Exercises 1.6a and 1.6b.
b. Exercises 1.6c and 1.6f.

Copyright 2013 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from
the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to
remove additional content at any time if subsequent rights restrictions require it.