文档介绍：Chapter 6 Languages: Finite State Machines
Wen-Hsiang Lu (盧文祥)
Department puter Science and Information Engineering,
National Cheng Kung University
2005/04/25
1
Chap 6 Languages: Finite State Machines
Language: The Set Theory of Strings
A finite state machine, which is an abstract model, has a finite number of internal states where the machine remembers certain information when it is in a particular state.
Strings: Sequence of symbols (characters) play a key role in the processing of information by puter.
∑ denote a nonempty finite set of symbols, collectively called an alphabet. ., ∑= {0, 1}, ∑= {a, b, c, d, e}.
Definition : If ∑ is an alphabet and , we define the powers of ∑ recursively as follows:
2
Chap 6 Languages: Finite State Machines
Language: The Set Theory of Strings
Example : Let ∑ an alphabet.
Definition : For an alphabet ∑ we define ∑0 ={ }, where denotes the empty string, ., the string consisting of no symbols taken from ∑.
Definition : If ∑ is an alphabet, then
3
Chap 6 Languages: Finite State Machines
Language: The Set Theory of Strings
Example : Let ∑= {0,1} the set ∑* consists of all finite strings of 0’s and 1’s together with the empty string.
If ∑= {ß,0,1,…,9,+,-,/,}, where ß denotes the blank (space). Here in ∑* we find familiar arithmetic expression such as (7+5)/(2-3).
Definition :
4
Chap 6 Languages: Finite State Machines
Language: The Set Theory of Strings
Definition :
Definition :
5
Chap 6 Languages: Finite State Machines
Language: The Set Theory of Strings
Definition :
Definition :
Definition :
6
Chap 6 Languages: Finite State Machines
Language: The Set Theory of Strings
Definition :
Example :
With ∑ the alphabet of 26 letters, 10 digits, and the special symbols used in a given implementation of C++, the collection of executable programs for that implementation constitutes a language.
In the same situation, each executable program could be considered a languag