```Deterministic FA/ PDA
Sequential Machine Theory
Prof. K. J. Hintz
Department of Electrical and Computer
Engineering
Lecture 4
Updated by Marek Perkowski
Numerical Acceptor
A Non-intuitive Concept of a Language Is
One Which Can Accept Binary Arithmetic
Values, e.g. L   x  B * : x  5 n, n  0 
4
0
1
0
1
0
1
2
1
1
0
5
1
0
3
Moret, Theory of Computation
Check all strings, from shortest that are accepted.
What is their language?
Languages Accepted by FA
• The Class of Languages Accepted by a
Deterministic or Nondeterministic FA Is
Closed Under
–
–
–
–
–
Union
Concatenation
Kleene Star
Complementation
Intersection
Union of Languages
L = L
1
L
since languages are sets of strings
2
M1
e
>
F = F1  F 2
e
M2
Final States of N D FA
Concatenation of Languages
L = L1L
2
A ny elem ent of L
w ith an elem ent of L
>
e
F = F2
1
can be concatenated
2
S1 M1 F1
e
S1 M2 F2
Final States of N D FA
Kleene Star of Languages
L = L1*
A ny elem ent of L
e
>
1
can be K leene Starred
e
e
S1
q0
F = F1  q 0
M1
F1
Final States of NDFA
Difference of Languages
L = L1  L 2
L1
F = F1  F 2
since languages
are sets of strings
L2
Final States of N D FA
Intersection of Languages
L = L
1
L
L1
2
since languages are sets of strings
L
L2
F =  F1  F2    F1  F2    F2  F1 
Final States of NDFA
I*
Languages and FA
• Kleene’s Theorem
– A Language Is Regular iff It Is Accepted by a
Deterministic or Nondeterministic Finite
Automata
• A Regular Language Is One Which Can Be
Defined by a Regular Expression
– Not all languages are regular
Give examples of languages
that are not regular
Context Free Languages
• Up Until Now we learned the following:
R egular E x pression  R egular Languages  D F A  N D F A
But This Is a Limited Class of Languages
• There Are Other Context-Free Languages
Which Cannot Be Recognized by a DFA
• There Are Other Types of Machines Which
Can Accept More Context-Free Languages
A Non-Regular Language
• Since a Language, L, Is a Subset of the Set
of All Strings, I*, Are There Some Strings
Which Cannot Be Produced by a Regular
Expression or Recognized by a DFA? Yes,
e.g.,
n
n
L  a b : n  0 
n
n
a b Regular?
• Theorem1: Let L be an infinite regular
language. Then there are strings x, y, and z
such that y  e and x yn z  L for each n  0
– Proof based on pigeonhole principle
• If there are n + 1 pigeons and n pigeonholes, then at
least two pigeons must be in the same hole
– If a string has more characters than there are
states in the language recognizer, then some
state must be entered more than once
1
Lewis & Papadimitriou, Elements of the Theory of Computation
n
n
a b Regular?
L  a b : n  0 
n
n
• Language Is Infinite, Therefore Theorem
Applies
• Is This Language Regular? If So, the
Theorem Must Apply
• Three Cases to Study
see next slides
n
n
a b Regular?
Case 1: y consists entirely of as
xa
p
p0
ya
q
q0
za b
r
s
r0
then L must contain
x y za
n
p  nq  r
b
s
n0
at most one of these strings can have an
equal number
of a s and b s
n
n
a b Regular?
Case 2: y consists entirely of bs
Similar argument to Case 1
n
n
a b Regular?
Case 3: y contains both as and bs
For n > 1, x yn z has an occurrence of b
preceding an occurrence of a and
therefore cannot be in L
Context Free Grammars: idea
• A More General Way to Describe and/or
Generate Languages
• Context-Free
– Replacement Rules Can Be Applied
Independently of the Preceding or Following
Elements. A  aa B  q
abA aB c  ab aa aB c  ab aa aqc
abA ac  ab A aqc  ab aa aqc
Context Free Grammar: definition
A Quadruple, ( I, , R, s) where
I

R
An alphabet
A set of terminals,   I
A finite set of rules, a subset of the
crossproduct of the set of non-terminals
and all strings,
R  I    I *
Context Free Grammar: definition
cont
s
The start symbol, a non-terminal
s  I  
I
AND ...

The set of non-terminals
Context Free Grammar: definition
cont
A I  
For All Non-terminals,
u I*
And Strings
The Grammar, G, Maps the Non-Terminals to
Strings
A   u
G
for strings
and non-terminals
u, v, x, y, v’  I*
A I  
Context Free Grammar: definition of
G-related
u is G-related to v
u   v
G
iff
u=xAy
v = x v’ y
and
A   v 
G
Context Free Grammar: the set of all
possible relations
• The relation,

, the * meaning the set of

G
all possible relations, is
– reflexive
– transitive
– has closure
u   u
G
u  v,
v  w,
I*
th en ,
G
u w
Context Free Language
• The Language Generated by the Context
Free Grammar, G, Is the Set of Strings
Which Map From the Start Symbol, s,
Under the Reflexive, Transitive, and Closed
Relation,

Language  G    w  I * :



s w 
G

Context Free Language
• A Context Free Language Is One Which
Can Be Generated by a Context Free
Grammar, and,
• The Context Free Grammar (CFG) Can Be
Used to Generate Strings of the Language
A Derivation Example
• The Steps in Applying the Rules From the
Start Symbol to Any String Is Called a
Derivation in G, e.g.,
I 
 


a , b, c, d , r , p, q, t , v , w
a , b, c, d , r


s w
 p  ra 
 q  ab 


R   t  cad 
 v  qp 


 w  vtv 
s w
 vtv
 qptqp
 qratqra
 abratabra
Pushdown Automata
• All Context-Free Languages can Be Recognized
by a PDA
• { an bn } Is Context-Free, but Not Regular
– Problem is same number of as and bs
• PDA Assumes
– An unlimited memory in the form of a stack, LIFO
– The machine only has access to the top of the stack.
Pushdown Automata:
formal definition
A PDA is a Sextuple,
PDA 
S
I



S , I ,  ,  , s, F ,
w here
A finite set of S tates
 inputs  , alphabet
 stack sym bols 
A non - determ inistic push - dow n relation
s
T he unique start state
F

final states

Pushdown Relation
 s are w ritten as
 

S  I * *    S   *

  present state, input string, top of stack  ,

 


 nex t state, new top o f stack  
where
“top of stack”
is replaced by
“new top of stack.”
Pushdown Relation Example

p ,  ,  ,  q , 


R eplace th e  on top of the
x
stack w ith 

x
s=p
s=q


p ,  ,  ,  q , a

push, i. e., replace the null
on the top of the stack w ith a
x
a
x
s=p
s=q
PDA Properties
• One Can Have the Same State Before and
After a Transition, but Have Different Stack
Contents Which Makes It NonDeterministic
  p , i,   

p, 

• State Changes May Occur in the Absence of
an Input, but Only If the Stack Is Not
Empty. i.e., non-causal behavior.
PDA Properties: what is the state of
PDA?
• The “State” of the PDA Is Determined Not
Only by S, and Not Only by the Top-ofStack, but Rather by Both the Current State
and the Complete Contents of the Stack, x
• This “State of the PDA” Is Called the
“Configuration of the PDA”
PDA Notation
• The Input May Cause the PDA to Change
From Configuration 1 to Configuration 2
 s1 , x 1 
y

 s2 , x 2 
w here
y I*
s1 , s 2  S
x 1 , x 2   *, the set o f all possible stack contents
PDA Recognizer
• A string w  I* is accepted by a PDA
iff
 some final state, s f  F ,
and some string of stack symbols,
where the input string, w  I *
such that
w
 s 0 ,    s f , 
may occur
 *
PDA Example*
A Machine to Recognize Strings of the Form
wcwR
i. e. ,
L 

* Lewis & Papadimitriou, pg. 114
w cw
R
: w   a, b

*

PDA Example
wcwR Can Be Represented by a Context Free
Grammar,
G   I,  , R , S 
w h ere
I

R
 S , a , b, c 
 a , b, c 
 S  aSa ,

 S  b S b,
 S  c






Equivalent NPDA
wcwR can be represented by a NPDA where







  




 


p ,  ,  ,  q , S

q ,  , S ,  q , a S a


q ,  , S ,  q , b S b


q ,  , S ,  q , c


q , a , a ,  q , 


q , b , b ,  q , 


q , c , c ,  q , 

 T1 , p u sh n o n - term in al 

 T 2 , ex p an d N T o n T O S 
 T3 , ex p an d N T o n T O S 


 T 4 , rep lace N T w ith c 

 T5 , p o p a


 T6 , p o p b

 T7 , p o p c

Is abccba Accepted?
Present
State
Input
p
abccba
e
-
Initial Conf
q
abccba
S
T1
Push NT
q
abccba
aSa
T2
Pick
T2/T3/T4
q
bccba
Sa
T5
pop a
Stack
Transition
(Top on Left)
used
Is abccba Accepted?
Present
State
Input
q
bccba
bSba
T3
Pick
T2/T3/T4
q
ccba
Sba
T6
pop b
q
ccba
cba
T4
replace NT
with c
q
cba
ba
T7
pop c
Stack
Transition
(Top on Left)
used
Is abccba Accepted?
The machine halts with unread inputs since
there is no

q , c , b  ,  next state, top of stack
to be executed.

Is bacab Accepted?
Present
State
Input
p
bacab
e
-
Initial Conf
q
bacab
S
T1
Push NT
q
bacab
bSb
T3
Pick
T2/T3/T4
q
acab
Sb
T6
pop b
Stack
Transition
(Top on Left)
used
Is bacab Accepted?
Present
State
Input
q
acab
aSab
T2
Pick
T2/T3/T4
q
cab
Sab
T5
pop a
q
cab
cab
T4
replace NT
with c
q
ab
ab
T7
pop c
Stack
Transition
(Top on Left)
used
Is bacab Accepted?
Present
State
Input
Stack
Transition
(Top on Left)
used
q
b
b
T5
pop a
q
e
e
T6
pop b
The machine halts with no unread input and
nothing on the stack, therefore,
bacab  language wcwR.
```