? Note: If the character order is not same, the string is different as well. For example, string “ab”and “ba”are not same. 001 and 010 are different
string.
bc .
.
zhangjing@
7
? 7.Product of string A and B
A and B are strings, the product of them is
AB=｛xy|(x∈A)∧(y∈B)｝
This means that AB is the set where x
……
xn=xx…x=xn-1x=xxn-1
xn is the n power of x
x0=ε
There is x=aTb, so the power of x and length of it are as follows.
x0=ε
| x0|=0
x1= aTb
| x1|=3
x2= aTb aTb
| x2|=6
? 2. String String is a sequence of characters, empty string can be represented byε,Usually small letters represent string.
zh , If there is alphabet A= ｛a, b, c｝,
x3= aTb aTb aTb
| x3|=9
zhangjing@
6
? 6.Head and tail of string
z=xy is string, the head of z is x, the tail of z is
y. if y≠ε, we call the x is true head of z. Similarly,
The characters of it are a, b, c .
The strings are a, b, c, ab, ac, aa, abc , …
Alphabet B= ｛0，1｝, the characters correspond to it are 0,1
The strings are 0 ，1，00，01，10，11， 000，…，01000，…
zhangjing@
2
String
? 1.Alphabet – finite character set , and it is nonempty set. For example, A= ｛a, b, c, … , z ｝, B=｛0, 1｝, A and B are alphabets.
.
zhangjing@
4
? 3. String Length
The length of string is the number of characters.
The string is x, the length of string is |x|. Take alphabet B for example, |01|=2 ，|000|=3 ，
Chapter 2
Grammar and Formal Language
Zhang Jing, Yu SiLiang College of Computer Science & Technology
Harbin Engineering University
? The goal of this chapter is to help readers to review some basic knowledge of mathematics that is related with the theory of compiler, and understand the mathematics symbolic language—formal language. In specific, we shall talk about the concepts of string, grammar, parser tree, formal language and so on. All the concepts are the basic knowledge for reader and will benefit them to go through the following chapters.
string x and y .
.
If there are x=abc ，y=de, then
xy=abcde，yx=deabc
Note : εx=xε=x
zhangjing@
5
? 5.Power of string
If x is string, then
x2=xx
x3=xxx
|01000|=5, The length of null string, |ε|= 0
? 4.Connection of string
There are strings x and y, write down y after x,
namely, “xy”w,e call “xy”as the connection of
belongs to A and y belongs to B
.
There are set A=｛a, b｝, B=｛0,1｝, so,
AB=｛a0, a1, b0, b1｝
if x≠ε, y is the tail of z and it is true
tail.
.
There is string of u = abc, so the heads of u areε、
a、ab、abc, true head of it are ε、a、ab, the tails
of u areε、c、bc、abc, true tails of it are ε、c、