Finite-State Machines with No Output
Ying Lu
Based on Slides by Elsa L Gunter, NJIT,
Costas Busch, and Longin Jan Latecki,
Temple University
Kleene closure
• A and B are two sets of strings.
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}
• A0={λ}, where λ represents the empty string
An+1=AnA
for n=0,1,2,…
Let A be any set of strings formed of characters in V.
Kleene closure of A, denoted by A*, is

A 
*
A
k
k 0
Examples:
If C={11}, then C*={12n: n=0,1,2,…}
If B={0,1}, then B*={all binary strings}.
Finite State Automata
• A FSA 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 automaton 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 automaton 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 
 s 2
a
• Is read ‘In state s1 on input “a” go to state s2’
• At the 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
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
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
Language Accepted by FSAs
• For a FSA
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 FSAs
• If a FSA has for every state exactly one
edge for each letter in alphabet then
FSA is deterministic
• In general a FSA is non-deterministic.
• Deterministic FSA special kind of nondeterministic FSA
Example FSA
• Deterministic FSA
• Regular expression: (0  1)* 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 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
NFSA
FSA
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
}
In-Class Exercise
• Construct a finite-state automaton that
recognizes the set of bit strings consisting of
a 0 followed by a string with an odd number
of 1s.
Appendix
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
Descargar

Programming Language Concepts (CIS 280)