Mathematical Foundation of Computer Science

DHARM

INTRODUCTION TO LANGUAGES AND FINITE AUTOMATA 187

(iii)

PPQ

QPQQ

(^01)
State Input SymbolInputSymbol
PQ P Q
7.4 Construct the finite automata for the language Ln (for n ≥ 1), i.e.,
Ln = {x ∈ {0, 1}/|x| = n and the nth symbol from the right in x is 1}
7.5 Let x be a string in {0, 1} of length n. describe the finite automata that accepts the string x and
no other strings. Also determine how many states are required.
7.6 Describe the language for each of the finite automatons shown in Fig. 7.23
q 0 q 2
0
q 1
1
0 0, 1
()a
1
q 0 q 2
0
q 1
1
0
()b
1
q 3
0
1, 0
1
P
1 0
0
()c
1
Q R
S
1
1
1
0
0