A
alphabet, 100
ambiguous language/ambiguous grammar, 239–241
removing of, 242
automaton
block diagram or mechanical diagram of finite, 120–121
B
backtracking, 245
boolean values, 4
C
Cartesian product, 101
Chomsky classification of grammar, 102–103
Chomsky Hierarchy, 102–103, 232
Chomsky normal form (CNF), 254
closed compatible, 31
closed covering, 31
combinational circuits, 2
communication language, 1
finding minimal machine from, 31–34
concatenation, 101
context free grammar (CFG), 232
ambiguous, 241
for , 234
for regular expression (0 + 1)* 01*, 233
removing useless symbols from, 247–248
for string [abba(baa)naab(aaba)n | n ≥ 0], 234
for a string of equal number of binary digits, 233–234
context free language (CFL)
application of, 271
closure properties of, 264–265
decision algorithms for, 269–271
Ogden's lemma for, 269
context-sensitive grammar, 112
contracted table method, 47–49, 51–52
D
decision algorithms for CFLs, 269–271
definite memory, 50
derivation trees, 236
deterministic finite automata (DFA), 123, 160
digital function
of two input two output sequence detector for every 1001 sequence, 8
of two input two output sequence detector for every 1010 sequence, 10
direct left-recursion, 243
distinguishable state, 151
distinguishing sequence, 18
D'Morgan's theorem, 217
E
equivalence relation, 101
equivalent partition
definition, 19
equivalent state, 151
F
finite automata, 119
by algebraic method using Arden's theorem, 187–190
applications, 161
conditions for declaring a String, 121–123
construction from a regular grammar, 262–264
deterministic, 123
graphical representation of, 119
minimization of, 151
nondeterministic, 123
tabular format of, 120
finite memory machine
definition, 38
testing table and testing graph for, 38–39, 44–47
finite non-empty set of states, 119
finite state machine
formal language and automata theory (FLAT), 1
G
grammar for programming language, 102
grammar of automata, 102
language generated by, 104–112
machine format for different, 103
Greibach normal form (GNF), 258
I
identities, 185
implied pair, 47
implied pair machine, 54
inaccessible state, 151
incompletely specified machine, 23–24
indirect/hidden left-recursion, 243
information lossless machine, 52
testing table for information lossless, 56–57, 59
information transmission theory, 52
inputs, of a synchronous sequential machine, 2
instantaneous description (ID), 292
intersection, 101
inverse machine, 60
K
k-equivalent state, 151
Kleene's Closure, 183
L
left-linear grammar, 208
left most derivation, 235
left recursive grammar
conversion to non-left recursive grammar, 243–244
lossless machine, 56
M
Mealy machine, 134
complement of binary number, 136
converting to a Moore machine by tabular format, 140–144
converting to a Moore machine by transitional format, 147–150
residue mod-3 for each binary string treated as binary integer of, 137
tabular representation of, 134
transitional diagram representation of, 136
merger table, 35
construction of, 35
minimum state automaton, from transitional table, 152–155
modulo 3 binary counter, 11–14
circuit diagram, 14
state diagram, 11
state table, 12
using flip flop (T flip flop and SR flip flop), 12–14
modulo 8 binary counter
circuit diagram, 16
excitation table, 15
state diagram, 14
using SR flip flop, 16
Moore machine, 134
converting to a Mealy machine by tabular format, 138–140
converting to a Mealy machine by transitional format, 144–146
counting of occurrence of substring aba, 137–138
residue mod-3 for each binary string treated as binary integer of, 136–137
tabular representation of, 135
transitional diagram representation of, 136
Myhill Nerode theorem, 155–160
N
nondeterministic finite automata (NFA), 123
ε (null) move or transaction, 128–132
ε (null) move or transaction to DFA, 196–202
process of converting to DFA, 124–128
non-generating symbols, 246
non-reachable symbols, 246–247
non-unit production, 249
normal form of a grammar, 254
null production, 251
O
Ogden's lemma for CFL, 269
order of definiteness of the machine, 47
output alphabet set, 118
output compatible machine, 54
outputs, of a synchronous sequential machine, 2
P
palindrome, 310
parse tree, 236
from a CFG, 236
for generating string 0100110, 236–237
for generating string 11001010, 237–238
for string aabbaa, 238
parsing, 236
power set, 101
prefix of a string, 100
production rules, 104
proper prefixes, 100
proper suffixes, 100
pumping lemma, for regular expression, 208–209
to prove that certain sets are not regular, 210–214
pumping lemma for CFL, 265–269
pushdown automata (PDA), 291
conditions to declare a string accepted by, 293
of a context free grammar, 311–315
deterministic PDA (DPDA), 308
graphical notation of, 316–317
mathematical notation for, 292
need for, 292
non-deterministic PDA (NPDA), 308–310
R
reflexive relation, 101
regular expression
construction of finite automata equivalent to, 191–196
definition, 182
formal recursive definition of, 182
Pumping Lemma for, 208
right-linear grammar, 208
right-most derivation, 235–236
S
set, 101
set of input alphabet, 118
single-state input-output combination, 44
stack, 292
stack symbol, 293
state assignment
modulo 8 binary counter, 15–16
two input two output sequence detector for every 1001 sequence, 8
two input two output sequence detector for every 1010 sequence, 10
state diagram, 3
state graph, 3
for binary substractor, 5
‘State' Q, 118
modulo 8 binary counter, 14–15
two input two output sequence detector for every 1001 sequence, 8
two input two output sequence detector for every 1010 sequence, 10
string, 100
substring of a string, 100
suffix of a string, 100
symbol, 100
symmetric relation, 101
synchronization, 2
synchronizing tree method, 47–48, 50–51
synchronous circuit, 2
synchronous sequential machine, 2
T
testing graph, for definite memory, 47–48
testing table and testing graph, for finite memory machine, 38–44
of information lossless machine, 54–55
testing table-testing graph for definiteness method, 47–50
theory of computation, 1
transitional function δ, 215, 294, 310
transitional function mapping, 123
transitive relation, 101
Turing machine
to accept string L = (a,b)*, where N(a) + N(b) = even, 342
to accept the language L = anb2n n>0, 345–346
basics of, 331
concatenation operation on two strings w1 and w2, 341
design for language L = anbncn, where n ≥ 1, 339–340
design for string 00, 343
ID for string 'aaabbb' with tape symbols, 333–336
ID for string ‘abaaaaba' with tape symbols, 336–338
IDs for null string, ‘a', 'aba and ‘baab', 338–339
instantaneous description (ID) of, 332
mechanical diagram, 332
for performing 1's complement operation on binary string, 344
for performing 2's complement operation on binary string, 344–345
to perform the function f(x) = x + 1, 343
to perform the operation f(x,y) = x – y, where x > y, 341–342
for set of all strings with equal number of ‘a' and ‘b', 345
significance of, 331
7 touples of, 331
transitional presentation of, 346–347
U
union, 101
unit production, 249
useless symbols, 246
V
3.143.5.15