Index

A

alphabet, 100

ambiguous language/ambiguous grammar, 239–241

problems with, 241–242

removing of, 242

automaton

block diagram or mechanical diagram of finite, 120–121

characteristics of, 118–119

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

compatibility graph, 30–31

finding minimal machine from, 31–34

concatenation, 101

context free grammar (CFG), 232

ambiguous, 241

for , 234

convertion to CNF, 254–257

convertion to GNF, 258–262

language , 234–235

for language L = , 232–233

for RE (011 + 1)* (01)*, 233

for regular expression (0 + 1)* 01*, 233

removing useless symbols from, 247–248

simplification of, 246–254

for string [abba(baa)ⁿaab(aaba)ⁿ | 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

pumping lemma for, 265–269

context-sensitive grammar, 112

contracted table method, 47–49, 51–52

D

dead state, 133, 151

decision algorithms for CFLs, 269–271

definite memory, 50

derivation trees, 236

deterministic finite automata (DFA), 123, 160

equivalence of two, 202–203

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

example, 19–23

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

equivalence of two, 202–203

graphical representation of, 119

minimization of, 151

nondeterministic, 123

tabular format of, 120

two-way, 160–161

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

definition, 16–17

limitations, 17–18

formal language and automata theory (FLAT), 1

full binary adder, 3–4

full binary substractor, 4–5

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

process of testing, 54–56

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

minimal, 61–63

K

k-equivalent state, 151

Kleene's Closure, 183

L

left factoring, 245–246

left-linear grammar, 208

left most derivation, 235

left recursive grammar

conversion to non-left recursive grammar, 243–244

removal of, 244–245

lossless machine, 56

lossy machine, 53–54

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 graph, 26–30

merger table, 35

construction of, 35

examples, 35–38

minimal machine, 25–26

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 assignment, 15–16

state diagram, 14

state table, 14–15

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

Moore's proposal, 243–244

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

removal of, 251–254

O

Ogden's lemma for CFL, 269

order of definiteness of the machine, 47

order of losslessness, 54–56

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

programming language, 1, 102

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

examples, 294–307

graphical notation of, 316–317

language accepted by, 293–294

mathematical notation for, 292

need for, 292

non-deterministic PDA (NPDA), 308–310

R

reflexive relation, 101

regular expression

basic operations on, 182–183

closure property, 214–217

complement of, 216–217

construction of, 184–185

construction of finite automata equivalent to, 191–196

definition, 182

in English language, 183–184

equivalence of two, 203–208

formal recursive definition of, 182

identities of, 185–187

Pumping Lemma for, 208

right-linear grammar, 208

right-most derivation, 235–236

S

sequence detector, 6–7

sequential circuits, 2, 5

set, 101

set of input alphabet, 118

simplified machine, 24–25

single-state input-output combination, 44

stack, 292

stack symbol, 293

state assignment

modulo 8 binary counter, 15–16

state assignments, 5–6, 8–9

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

for Mod 3 binary counter, 11

modulo 8 binary counter, 14

state graph, 3

for binary substractor, 5

‘State' Q, 118

state table, 3, 8

for Mod 3 binary counter, 12

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

transitional system, 121–123

transitive relation, 101

Turing machine

to accept string L = (a,b)*, where N(a) + N(b) = even, 342

to accept the language L = aⁿb2ⁿ n>0, 345–346

basics of, 331

concatenation operation on two strings w1 and w2, 341

design for language L = aⁿbⁿcⁿ, 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

for infinite loop, 342–343

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

removal of, 250–251

useless symbols, 246

V

vanishing connection matrix method, 39–42, 45–47