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