Finite-State Machines with No Output
Longin Jan Latecki
Temple University
Based on Slides by Elsa L Gunter, NJIT,
and by Costas Busch
Kleene closure
• A and B are subsets of V*, where V is a
vocabulary
The concatenation of A and B is
AB={xy: x string in A and y string in B}
• Example: A={0, 11} and B={1, 10, 110}
AB={01,010,0110,111,1110,11110}
• What is BA?
• A0={λ}
An+1=AnA
for n=0,1,2,…
Let A be any subset of V*.
Kleene closure of A, denoted by A*, is

A 
*
A
k
k 0
Examples:
If C={11}, C*={12n: n=0,1,2,…}
If B={0,1}, B*=V*.
Regular Expressions
Regular expressions
describe regular languages
Example: ( a  b  c ) *
describes the language
a , bc *   , a , bc , aa , abc , bca ,... 
Recursive Definition
Primitive regular expressions:  ,  , 
Given regular expressions r1 and r2
r1  r2
r1  r2
r1 *
 r1 
Are regular expressions
Examples
A regular expression:
 a  b  c  * ( c   )
Not a regular expression:
a  b  
Languages of Regular
Expressions
L  r  : language of regular expression r
Example
L  ( a  b  c ) *    , a , bc , aa , abc , bca ,... 
Definition
For primitive regular expressions:
L    
L      
L  a   a 
Definition (continued)
For regular expressions r1 and r2
L  r1  r2   L  r1   L  r2 
L  r1  r2   L  r1  L  r2 
L  r1 *    L  r1   *
L   r1    L  r1 
Example
Regular expression:  a  b   a *
L  a  b   a *   L  a  b  L  a * 
 L a  b  L a *
  L  a   L b   L  a  *
 a   b  a  *
 a , b   , a , aa , aaa ,... 
 a , aa , aaa ,..., b , ba , baa ,... 
Example
Regular expression r   a  b  *  a  bb 
L  r   a , bb , aa , abb , ba , bbb ,... 
Example
r   aa  *  bb  * b
Regular expression
L r   {a
2n 2m
b
b:
n , m  0}
Example
Regular expression r  ( 0  1) * 00 ( 0  1) *
L (r ) = { all strings with at least
two consecutive 0 }
Example
Regular expression r  (1  01 ) * ( 0   )
L (r ) = { all strings without
two consecutive 0 }
Equivalent Regular Expressions
• Definition:
•
Regular expressions r1 and
•
are equivalent if L ( r1 )  L ( r2 )
r2
Example
L = { all strings without
two consecutive 0 }
•
r1  (1  01 ) * ( 0   )
r2  (1 * 011 *) * ( 0   )  1 * ( 0   )
L ( r1 )  L ( r2 )  L
r1 and r2
are equivalent
regular expr.
Example: Lexing
• Regular expressions good for
describing lexemes (words) in a
programming language
– Identifier = (a  b  …  z  A  B  …  Z)
(a  b  …  z  A  B  …  Z  0  1 
…  9  _  ‘ )*
– Digit = (0  1  …  9)
Implementing Regular
Expressions
• Regular expressions, regular grammars
reasonable way to generates strings in
language
• Not so good for recognizing when a
string is in language
• Regular expressions: which option to
choose, how many repetitions to make
• Answer: finite state automata
Finite (State) Automata
• A FA is similar to a compiler in that:
– A compiler recognizes legal programs in some (source) language.
– A finite-state machine recognizes legal strings in some language.
• Example: Pascal Identifiers
– sequences of one or more letters or digits,
starting with a letter:
letter | digit
letter
S
A
Finite Automaton
•
Input
String
Finite
Automaton
Output
“Accept”
or
“Reject”
Finite State Automata
• A finite state automation over an alphabet
is illustrated by a state diagram:
– a directed graph
– edges are labeled with elements of alphabet,
– some nodes (or states), marked as final
– one node marked as start state
Transition Graph
a,b
•
q5
b
q0 a
a
q1 b
initial
state
state
a
q2 b
b
q3 a
transition
a,b
q4
accepting
state
Initial Configuration
a b b a
•
Input String
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
Reading the Input
a b b a
•
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
•
a b b a
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
•
a b b a
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
•
a b b a
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
Input finished
a b b a
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
accept
Rejection
a b a
•
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
•
a b a
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
•
a b a
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
•
a b a
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
Input finished
a b a
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
reject
a,b
q4
Another Rejection

•
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4

•
a,b
q5
b
q0 a
reject
a
q1 b
a
q2 b
b
q3 a
a,b
q4
Another Example
a
a b
a,b
a
q0
b
q1
a,b
q2
a
a b
a,b
a
q0
b
q1
a,b
q2
a
a b
a,b
a
q0
b
q1
a,b
q2
a
a b
a,b
a
q0
b
q1
a,b
q2
Input finished
a
a b
a
q0
a,b
accept
b
q1
a,b
q2
Rejection Example
b
a b
a,b
a
q0
b
q1
a,b
q2
b
a b
a,b
a
q0
b
q1
a,b
q2
b
a b
a,b
a
q0
b
q1
a,b
q2
b
a b
a,b
a
q0
b
q1
a,b
q2
Input finished
b
a b
a,b
a
q0
b
q1
a,b
q2
reject
Finite State Automata
• A finite state automation M=(S,Σ,δ,s0,F)
consists of
• a finite set S of states,
• a finite input alphabet Σ,
• a state transition function δ: S x Σ  S,
• an initial state s0,
• F subset of S that represent the final states.
Finite Automata
• Transition
s1 a s2
• Is read ‘In state s1 on input “a” go to state s2’
• If end of input
– If in accepting state => accept
– Otherwise => reject
• If no transition possible (got stuck) => reject
• FSA = Finite State Automata
Input Alphabet
•

  a , b 
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
Set of States
Q
• Q  q 0 , q1 , q 2 , q 3 , q 4 , q 5 
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
Initial State
q0
•
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
Set of Accepting States
• F  q 4 
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
F
Transition Function 
•
 :S  S
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
  q 0 , a   q1
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
 q0 , b   q5
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
 q 2 , b   q3
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
Transition Function 

a
q0
q1
b
q5
q1
q5
q2
q2
q5
q3
q3
q4
q5
q4
q5
q5
q5
q5
q5
•
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
Exercise
Construct the state diagram for M=(S,Σ,δ,s0,F),
where S={s0, s1, s2, s3}, Σ={0,1}, F={s0, s3}
and the transition function δ :
state
s0
s1
s2
Input: 0
s0
s0
s0
Input: 1
s1
s2
s0
s3
s2
s1
Language accepted by FSA
• The language accepted by a FSA is the set of strings
accepted by the FSA.
• in the language of the FSM shown below:
x, tmp2, XyZzy, position27.
• not in the language of the FSM shown below:
• 123, a?, 13apples.
letter | digit
letter
S
A
Example:
• FSA that accepts three letter English words that begin with
p and end with d or t.
• Here we use the convenient notation of making the state
name match the input that has to be on the edge leading to
that state.
a
t
p
i
o
d
u
59
Example
L  M   abba 
M
•
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
accept
Example
L  M    , ab , abba 
M
•
a,b
q5
b
q0 a
accept
a
q1 b
a
q2 b
accept
b
q3 a
a,b
q4
accept
Example
•
L  M   { a b : n  0}
n
a,b
a
q0
b
q1
accept
a,b
q2
trap state
Extended Transition Function 
 * : Q  *  Q
•
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
*
 *  q 0 , ab   q 2
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
 *  q 0 , abba   q 4
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
 *  q 0 , abbbaa   q 5
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
Observation: if there is a walk from q to q 
with label w then
 * q , w   q 
w
q
q
w   1 2   k
q
1
2
k
q
Example: There is a walk from q 0 to q 5
with label abbbaa
 *  q 0 , abbbaa   q 5
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
Recursive Definition
 * q ,    q
 *  q , w     ( * ( q , w ),  )
q
w
q1

q
 * q , w    q 
 ( q1 ,  )  q 
 *  q , w     ( q1 ,  )
 *  q , w     ( * ( q , w ),  )
 *  q , w   q1
 * q 0 , ab  
  * ( q 0 , a ), b  
   * q 0 ,  , a , b  
  q 0 , a , b  
 q 1 , b  
a,b
q2
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
Language Accepted by FAs
• For a FA
M  Q ,  ,  , q 0 , F 
• Language accepted by M :
•
L  M   w   * :  *  q 0 , w   F 
q0
w
q
q  F
Observation
• Language rejected by M :
L  M   w   * :  *  q 0 , w   F 
q0
w
q
q  F
Example
L  M  = { all strings with prefix ab }
•
a,b
q0
a
q1
b
a
q3
b
q2
accept
a,b
Example
•
L  M  = { all strings without
substring 001 }
1
0
0 ,1
1

0
0
0
00
1
001
Example
L ( M )  awa : w  a , b  *
a
b
•
b
q0
a
q2
q3
a
b
q4
a,b
Deterministic FSA’s
• If FSA has for every state exactly one
edge for each letter in alphabet then
FSA is deterministic
• In general FSA in non-deterministic.
• Deterministic FSA special kind of nondeterministic FSA
Example FSA
• Regular expression: (0  1)* 1
• Deterministic FSA
1
0
1
0
Example DFSA
• Regular expression: (0  1)* 1
• Accepts string 0 1 1 0 1
1
0
1
0
Example DFSA
• Regular expression: (0  1)* 1
• Accepts string 0 1 1 0 1
1
0
1
0
Example DFSA
• Regular expression: (0  1)* 1
• Accepts string 0 1 1 0 1
1
0
1
0
Example DFSA
• Regular expression: (0  1)* 1
• Accepts string 0 1 1 0 1
1
0
1
0
Example DFSA
• Regular expression: (0  1)* 1
• Accepts string 0 1 1 0 1
1
0
1
0
Example DFSA
• Regular expression: (0  1)* 1
• Accepts string 0 1 1 0 1
1
0
1
0
Example DFSA
• Regular expression: (0  1)* 1
• Accepts string 0 1 1 0 1
1
0
1
0
Example NFSA
• Regular expression: (0  1)* 1
• Non-deterministic FSA
0
1
1
Example NFSA
• Regular expression: (0 +
 1)* 1
• Accepts string 0 1 1 0 1
0
1
1
Example NFSA
• Regular expression: (0 +
 1)* 1
• Accepts string 0 1 1 0 1
0
1
1
Example NFSA
• Regular expression: (0 +
 1)* 1
• Accepts string 0 1 1 0 1
0
1
1
Example NFSA
• Regular expression: (0 +
 1)* 1
• Accepts string 0 1 1 0 1
• Guess
0
1
1
Example NFSA
• Regular expression: (0 +
 1)* 1
• Accepts string 0 1 1 0 1
• Backtrack
0
1
1
Example NFSA
• Regular expression: (0 +
 1)* 1
• Accepts string 0 1 1 0 1
• Guess again
0
1
1
Example NFSA
• Regular expression: (0 + 1)* 1
• Accepts string 0 1 1 0 1
• Guess
0
1
1
Example NFSA
• Regular expression: (0 +
 1)* 1
• Accepts string 0 1 1 0 1
• Backtrack
0
1
1
Example NFSA
• Regular expression: (0 +
 1)* 1
• Accepts string 0 1 1 0 1
• Guess again
0
1
1
Example NFSA
• Regular expression: (0 +
 1)* 1
• Accepts string 0 1 1 0 1
0
1
1
Example NFSA
• Regular expression: (0 +
 1)* 1
• Accepts string 0 1 1 0 1
• Guess (Hurray!!)
0
1
1
If a language L is recognized by
a nondeterministic FSA,
then L is recognized by a deterministic FSA
Example 9, p. 763
How to Implement an FSA
A table-driven approach:
• table:
– one row for each state in the machine, and
– one column for each possible character.
• Table[j][k]
– which state to go to from state j on character k,
– an empty entry corresponds to the machine getting
stuck.
The table-driven program for a
Deterministic FSA
state = S // S is the start state
repeat {
k = next character from the input
if (k == EOF) // the end of input
if state is a final state then accept
else reject
state = T[state,k]
if state = empty then reject // got stuck
}
Descargar

Programming Language Concepts (CIS 280)