CS 1104 Introduction to Computer Science

COMPILERS AND TRANSLATORS



This machine can accept only two strings: "ab" and "acd" and give the response "YES". All other strings would result in a "NO" reponse, meaning that they were not recognized.

We may also represent the "program" for a finite state machine in a table:

Current State
Current Character
Next State
=> 1
a
2
2
b
4 =>
2
c
3
3
d
4 =>
4
 
 

 

Every "command line" in the FSM table must be distinct in the first two columns (state, and character) so as to produce a DETERMINISTIC machine. While NON-deterministic machines do exist, they are not part of our study.

 

As the recognition process continues we can list the state transitions that are completed by listing each row in the transition table:

 

For the string "acd":

1
a
2
2
c
3
3
d
4
4 (exit)

 


[TOC]


© J.A.N. LEE
Last Updated 2000/03/28