DEBRE MARKOS UNIVERSITY
BURIE CAMPUS
DEPARTMENT COMPUTER
SCIENCES
FORMAL LANGUAGE THEORY
1
outlines
Introduction
Alphabet
Strings
Languages
Grammars
Automata
2
CHAPTER ONE
INTRODUCTION
Formal language is an abstract of the general
characteristic of programming language.
It is the set of all strings permitted by the rules of
formation.
It consists of a set of symbols and some rules of
formation by which these symbols can be
combined into entities called sentences.
3
Alphabet
It is finite set of symbols and denoted by
Example
1 = {a, b, c, d, …, z}: the set of letters in English
2 = {0, 1, …, 9}: the set of (base 10) digits
3 = {a, b, …, z, #}: the set of letters plus the
special symbol #
4 = {(, )}: the set of open and closed brackets
4
Strings
it is finite set of symbols over
We will use small alphabets: a, b
a
Strings
ab u ab
abba v bbbaaa
baba w abba
aaabbbaabab
5
String Operations
w a1a2 an abba
v b1b2 bm bbbaaa
Concatenation
wv a1a2 anb1b2 bm abbabbbaaa
6
w a1a2 an ababaaabbb
Reverse
R
w an a2a1 bbbaaababa
7
String Length
w a1a2 an
Length: w n
Examples: abba 4
aa 2
a 1
8
Recursive Definition of Length
For any letter: a 1
For any string wa : wa w 1
Example: abba abb 1
ab 1 1
a 111
1111
4 9
Length of Concatenation
uv u v
Example: u aab, u 3
v abaab, v 5
uv aababaab 8
uv u v 3 5 8
10
Empty String
A string with no letters:
Observations: 0
w w w
abba abba abba
11
Substring
Substring of string:
a subsequence of consecutive characters
String Substring
abbab ab
abbab abba
abbab b
abbab bbab
12
Prefix and Suffix
abbab
Prefixes Suffixes
abbab w uv
a bbab
prefix
ab bab
suffix
abb ab
abba b
abbab
13
Another Operation
n
w ww w
n
Example: abba abbaabba
2
0
Definition: w
abba
0
14
The * Operation
* : the set of all possible strings from
alphabet
a, b
* , a, b, aa, ab, ba, bb, aaa, aab,
15
The + Operation
: the set of all possible strings from
alphabet except
a, b
* , a, b, aa, ab, ba, bb, aaa, aab,
*
a, b, aa, ab, ba, bb, aaa, aab,
16
Language
A language is any subset of *
Example: a, b
* , a, b, aa, ab, ba, bb, aaa,
Languages:
a, aa, aab
{ , abba, baba, aa, ab, aaaaaa} 17
Another Example
n n
An infinite language L {a b : n 0}
ab L abb L
aabb
aaaaabbbbb
18
Operations on Languages
The usual set operations
a, ab, aaaa bb, ab {a, ab, bb, aaaa}
a, ab, aaaa bb, ab {ab}
a, ab, aaaa bb, ab a, aaaa
Complement: L * L
19
Reverse
R R
Definition: L {w : w L}
Examples: ab, aab, baba ba, baa, abab
R
n n
L {a b : n 0}
R n n
L {b a : n 0}
20
Concatenation
Definition: L1L2 xy : x L1, y L2
Example: a, ab, ba b, aa
ab, aaa, abb, abaa, bab, baaa
21
Another Operation
Definition: n
L LL L
n
a, b a, b a, b a, b
3
aaa, aab, aba, abb, baa, bab, bba, bbb
0
Special case: L
a , bba , aaa 0
22
Star-Closure (Kleene *)
0 1 2
Definition: L* L L L
Example:
,
a, bb,
a, bb *
aa , abb, bba , bbbb,
aaa, aabb, abba, abbbb,
23
Positive Closure
1 2
Definition: L L L
L *
a, bb,
a, bb aa, abb, bba, bbbb,
aaa, aabb, abba, abbbb,
24
Examples of language generated by RE
a | b = {a,b}
2- (a|b)a = {aa,ba}
3- (ab) | ε ={ab, ε}
4- ((a|b)a)* = {ε, aa,ba,aaaa,baba,....}
5- (a | c)*b(a|c)* ={b, abc, abaca, baaaac,
ccbaca, cccccb} (construct its DFA)
25
Grammar
Grammar is a mechanism to describe the languages.
A grammar (G) is defined as a quadruple
G = (V, T, S, P)
where
V = Finite set of objects called VARIABLES
T = Finite set of objects called TERMINAL SYMBOLS
S ∈ V = Start variables
P = Finite set of Productions.
A production rule P is of the form X Y
26
Con--
Given a grammar G defined by the production
rules
S ->AB
A ->Aa
B ->Bb
A-> a
B ->b
Show that the word w = a2b4 is L(G)
27
Automata
An abstract machine which can be used to implement
regular expressions .
Has a finite number of states, and a finite amount of
memory (i.e., the current state).
Can be represented by directed graphs or transition
tables
type of automata
Deterministic finite automata (DFA)
Non deterministic finite automata(NDFA)
28