1.3
The formal description of a DFA
M
is (
{
q1,
q1,
q1,
q1,
q5,
}
,
{
u,d
}
,
δ
,
q3
,
{
q3
}
)
,
where δ
is given by
the following table.
Give the state diagam of this machine.
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
}
b.
{
w
|
w
contains at least three 1s
}
c.
{
w
|
w
contains the substring 0101,
i.e., w = x0101y
for some
x
and
}
d.
{
w
|
w
has length at least 3 and its third symbol is 0
}
e.
{
w
|
w
starts with 0 and has even length, or starts with 1 and has odd length
}
f.
{
w
|
w
doesn't contain the substring 110
}
g.
{
w
|
the length of
w
is at most 5
}
h.
{
w
|
w
is any string except 11 and 111
}
i.
{
w
|
every odd position of
w
is a 1
}
j.
{
w
|
w
contains at least two 0s and at most one 1
}
k.
{
ε
,
0
}
l.
{
w
|
w
contains an even number of 0s, or contains
exactly two 1s
}
m.
The empty set
n.
All strings except the empty string
1.7 Give state diagrams of NFAs with the specified number
of states recognizing each language.
In all parts, the alphabet is
{ 0,1 }
a.
{
w
|
w
ends with 00
}
with three states
b.
The language of Exercise 1.6c with five states
c.
The language of Exercise 1.6l with six states
d.
The language
{
0
}
with two states
g.
The language
{
ε
}
with one state
h.
The language
0* with one state