q 4 is the final state.
Please note that this is an NFA as δ( , )
q
q
2
3
0 =
and δ( , )
q
q
2
3
1 = .
Ì Exam ple 1.2.2: Determine an NFA accepting the language
(a) L
x x a b c
1 =
∈
{ |
{ , , }
* and x contains the pattern abac}
(b) L
a
b
2 =
∪
{
}
*
*
Solu tion
(a)
(b)
Ì Exam ple 1.2.3: Determine an NFA accepting all strings over {0,1}
which end in 1 but does not contain the substring 00.
Solu tion
The conditions to be satisfied are:
(a) String should end in a 1
(b) String should not contain 00.
The NFA is shown in figure.
Ì Exam ple 1.2.4: Obtain an NFA which should accept a language L A ,
given by L
x a b
x
A = ∈
≥
{ { , } :| |
*
3 and third symbol of x from the right is
{‘a’}.
DFA and NFA
71
q 0
q 1
abac
a,b,c
a,b,c
q 0
q 1
q 2
a
b
λ
λ
q 0
q 1
q 2
1
1
0
1
q 1
q 2
q 3
q 4
1
0,1
0,1