Lec06 - Transitional Graphs and GTGs

Transition Graphs
Introducing the first non-deterministic but

simple theoretical machine: Transition Graph.
3
T
Relaxing the restrictions on

h
e
o
r
y
inputs
o
f
A
u  Let’s consider a very specialized FA that accepts only the
t word baa:
o
m
a
t
a
 Beginning at the start state, anything but the string baa

will drop down into the garbage collecting state and never
be seen again. Even the string baabb will fail.
 Hence the language accepted by this FA is L = {baa}
4
T
h
e Relaxing restrictions on
input
o
r
y
o
f  Let us relax the restriction that an FA can only read one letter
A from the input string at a time
u
t
o  Suppose we now allow a machine to read either one or two
m letters of the input string at a time. Then we may design a
a machine that accepts only the word baa with fewer states as the
t
a
one below:
5
T
h
e
Relax restrictions on input

o
r
y
o
f  If we go further to allow a machine to read up to three letters
A of the input string at a time, then we may design the machine
u accepting only the word baa with even fewer states as
t
o follows:
m
a
t
a
Chapter 6: Transition Graphs
TG for all words that contain a double letter

a,b a,b
aa,bb
– +
 baa?
 a choice, a decision
2 possible paths b|aa - accepted
b|a|a - rejected
1 way to crash ba|a – rejected
 The machine represents a language L. baa  L?
 For all w, w  L if there exists a path that arrives at a final
state.
1
ba ab
– +
baa 2 b
 baab? 2 possible paths, both end in a final state.

 DFAs had a unique path through the machine for every
input.
 Now some strings have no paths, some have several.
FA Definition
A finite automaton is a collection of three things:
1. A finite set of states, one of which is designated as

the initial state, called the start state, and some
(maybe none) of which are designated as final
states.
2. An alphabet Σ of possible input letters.
3. A finite set of transitions that tell for each state and

for each letter of the input alphabet which state to go
next.
TG Definition:
A Transition graph (TG), is a collection of the followings:

1. Finite number of states, at least one of which is start state
and some (maybe none) final states.
2. Finite set of input letters (Σ) from which input strings are
formed.
3. Finite set of transitions that show how to go from one state
to another based on reading specified substrings of input
letters, possibly even the null string (Λ).
 A successful path is a series of edges beginning at

some start state and ending at a final state.
 The concatenation of all the substrings that label the
edges in the path is a word accepted by this machine.
 The set of words accepted is the language of the
transition graph.
 Example:
1 abb 2 L 3 a 4
– +
aa
b
2 1 4
abbaab 1 3
abb L aa b
abbab crashes.
Many start states could be there in a TG

1
– L 1
a
a
b L 2 b
2– + – +
3 aba L 3 aba
–
 These two machines are clearly equivalent.

 Remark: Every finite automaton is a transition graph.
– +
L = {L}
L=
– L
+
abba –
baa
–
L = {L, abba, baa}

Some more TGs accepting the NULL string Λ
L = {Λ} L
+ +
L
L L
– + – +
All words ending in b: (a+b)*b
a,b a FA b
b
b –
– + +
a
transition graph:
Some words can fail, crash, and succeed: abab.
Chapter 6: Transition Graphs (Examples)
a,b
b
+
a
– a,b
b
a
+
aa b
b b b +
–
aa
Language EVEN-EVEN
FA: Transition Graph:

b
even a
even a aa,bb aa,bb
1+ 2 odd b
even b b ab,ba
+
a a a a ab,ba
balanced unbalanced
b
odd a
odd a 3 4
b odd b
even b
Generalized Transition Graph
(GTG)
Generalized Transition Graph (GTG)
A Generalized Transition Graph (GTG) is a collection of three
things:
1. Finite number of states, at least one of which is start state
and some (maybe none) final states.
2. Finite set of input letters (Σ) from which input strings are
formed.
3. Directed edges connecting some pair of states labeled with
a regular expression.
Note that in GTG, the labels of transition edges are
corresponding regular expressions
Gen Transition Graphs
Example 3: Words without 2 b’s in a row:

Gen Transition Graphs
 Example 4: Kleene Star Closure and Loops
Example 5: Σ = {a,b}
Consider the language L of strings of “beginning and
ending in different letters”
R.E = a(a + b)*b + b(a + b)*a
NonDeterminism
 We have already seen that in a TG, a particular
string of input letters may trace through the machine
on different paths, depending on our choice of
grouping.
 This figure shows part of some TG.
 The input string abb can go from state 3 to state 4, or

to state 5, depending on whether we read the letters
two and one, or all three at once.
Theory of Automata 23
NonDeterminism
 The ultimate path through the machine is NOT
determined by the input alone. Human choice
becomes a factor in selecting the path. The machine
does not make all its own determination.
 Therefore, we say that TGs are nondeterministic.
Theory of Automata 24
Choosing Transitions
Human choice becomes a factor in selecting the path;

Choices even with restriction of 1 letter per edge
8 …
a
… 7
b
9 …
b 8 …
1
0
… a
… 7
b
9 …
L
Nondeterministic
b 1
0
…
Review
 Understand differences between TGs and FAs
 Every FA is a TG but every TG is not an FA.
 Input may be traced on a TG on different paths
depending on our choice.
 Paths in TGs are not determined by the input
alone unlike in FAs.
 Non-determinism: human choice vs machine
choice

Lec06 - Transitional Graphs and GTGs

Uploaded by

Copyright:

Available Formats

Lec06 - Transitional Graphs and GTGs

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lec06 - Transitional Graphs and GTGs

Uploaded by

Copyright:

Available Formats

Transition Graphs

Introducing the first non-deterministic but

Relaxing the restrictions on

 Beginning at the start state, anything but the string baa

Relax restrictions on input

TG for all words that contain a double letter

 baab? 2 possible paths, both end in a final state.

A finite automaton is a collection of three things:

1. A finite set of states, one of which is designated as

2. An alphabet Σ of possible input letters.

3. A finite set of transitions that tell for each state and

A Transition graph (TG), is a collection of the followings:

 A successful path is a series of edges beginning at

Many start states could be there in a TG

 These two machines are clearly equivalent.

L = {L, abba, baa}

Some more TGs accepting the NULL string Λ

All words ending in b: (a+b)*b

FA: Transition Graph:

Example 3: Words without 2 b’s in a row:

 This figure shows part of some TG.

 The input string abb can go from state 3 to state 4, or

 Therefore, we say that TGs are nondeterministic.

Human choice becomes a factor in selecting the path;

You might also like