Introduction To: Formal Language Theory
Introduction To: Formal Language Theory
Introduction To: Formal Language Theory
highly flexible
quite powerful
Disadvantages
vague/unclear
inaccurate
ambiguous
Formal Language 4
Theory
Overview of languages: cont’d
Formal Languages
developed with strict rules
predefined syntax and semantics
accurate
unambiguous
Formal Language 5
Theory
Overview of languages: cont’d
<simple sentence>
Derivation tree for the simple sentence: A person entered the room.
Formal Language 7
Theory
Overview of languages: cont’d
Formal Language 8
Theory
Review of set theory and relations
Sets
A well defined collection of objects (called or elements)
members
Notation: a Є S a is an element of the set S
Operation
Let A and Bon
besets
two sets and U the universal set
Subset: A C B
Proper subset: A c B
Equality: A = B
Union: A U B
Intersection: A ∩ B
Set difference: A \ B or A – B
Complement: A’ or A bar
Formal Language 9
Theory
Set theory and relations: cont’d
Properties
Let A, B, C be sets and U the universal set
Associative property: A U (B U C) = ( A U B) U C
Commutative property: A U B = B U A
Definitions:
Let A be a set. The cardinality of set A is called the
cardinal number and denoted by |A| or #(A).
The set of all subsets of a set A is called the power set
of A, denoted by 2A.
Formal Language 10
Theory
Set theory and relations: cont’d
Definition:
Let S be a set. A collection {A1, A2, …, An} of subsets of S is called a partition
if Ai ∩ Aj = Ø, i≠j and S = A1 U A2 U … U An.
Ex. S = {1, 2, …, 10}
Let A1 ={1, 3, 5, 7, 9} and A2 ={2, 4, 6, 8, 10}, then {A1 , A2} = {{1, 3, 5, 7, 9},{2, 4,
6, 8, 10}} is a partition of S.
Q. Find other partitions of S
Countability
A finite set is countable
If the elements of set A can be associated with 1st,2nd, …, ith, … elements of
the set of Natural Numbers, then A is countable.
Note: that in this case A may not be finite.
Ex.
1. N = {1, 2, …, ith, …} is countable
2. Z = {…, -3, -2, -1, 0, 1, 2, 3, …} = {0, 1, -1, 2, -2, 3, -3, …} is countable
3. [0, 3] is uncountable (not countable)
Formal Language 11
Theory
Relations and functions
Relations
Definition: A relation R is a set of ordered of elements
pairs in S. (i.e is a subset of S X S)
Notation: (x, y) Є R or x R y
Properties of relations
Let R be a relation on a set A, then
a. R is reflexive if for all a Є A, a R a or (a, a) Є R
b. R is symmetric if a R b => b R a
c. R is transitive if a R b and b R c => a R c, for all a, b, c Є R
d. R is an equivalence relation if (a), (b) and (c) above hold.
Let R be an equivalence relation on set A and let a Є A, then
the equivalence class of a, denoted by [a], is defined as:
[a] = {b ЄA | a R b}
Formal Language 12
Theory
Relations and functions: cont’d
Examples:
Check whether the following relations are
reflexive, symmetric, and transitive
Functions
Definition: A function f from a set X to a set Y is a rule that
associates to every element x in X a unique element in Y,
which is denoted by f(x).
The element f(x) is called the image of x under f.
The function is denoted by f: X Y
Functions can be defined in the following two ways:
1. By giving the images of all elements of X
Ex. f:{1, 2, 3, 4} {2, 4, 6} can be defined by
f(1) = 2, f(2) = 4, f(3) = 6, f(4) = 6
2. By a computational rule which computes f(x) x is given
once
Ex. f:R R can be defined by f(x) = x2 + 2x + 1, x Є R (R =
the set of all real numbers)
Formal Language 14
Theory
Relations and functions: cont’d
Let f: A B be a function
1. f is an into(Injective) function if Rf C B
2. f is an onto(surjective) function if Rf = B
3. f is a one-to-one(bijective) function
if for x1 & x2 Є A, x1 ≠ x2 => f(x1) ≠ f(x2)
4. f is bijective (one-to-one correspondence) if it satisfies (2)
and (3) above.
Ex. f:Z Z is given by f(x) = 2x
Show that f is one-to-one but not onto.
Formal Language 15
Theory
Mathematical induction
Formal Language 16
Theory
Mathematical induction: cont’d
Solution:
Let Pn: 1+2+…+n = n(n+1)/2
Step1: for n = 1, P1 holds
Step2: for some kЄZ+, assume Pk is true
i.e. Pk: 1+2+…+k = k(k+1)/2
Step3: WTS Pk+1 is true
Pk+1 : 1+2+…+k+(k+1) = (k+1)(k+2)/2
: Pk + (k+1) = (k+1)(k+2)/2
: k(k+1)/2 + (k+1) = (k+1)(k+2)/2
: [k(k+1) + 2(k+2)]/2 = (k+1)(k+2)/2
: (k+1)(k+2)/2 = (k+1)(k+2)/2
Therefore, Pn holds for all n ЄZ+
Formal Language 17
Theory
Graphs and trees
Graphs
Definition: A graph (undirected graph) consists
of:
a. A non-empty set v called the set of vertices,
b. A set E called the set of edges, and
c. A map Φ (phi) which assigns to every edge a unique
unordered pair of vertices
e1 e6
v2 e1 = {v1, v2}
v1
e2 = {v1, v3}
e2 e3 e5 …
e6 = {v2, v2} (a self loop)
v3 e4 v4
Formal Language 18
Theory
Graphs and trees: cont’d
e1
v2 e1 = (v1, v2)
v1
e3 v1 : a predecessor of v2
e2 e5
v2 a successor of v1
v4 :
v3 e4
Formal Language 19
Theory
Graphs and trees: cont’d
Formal Language 20
Theory
Graphs and trees: cont’d
Formal Language 21
Theory
Graphs and trees: cont’d
Trees
Definition: A graph (directed or undirected) is
called a tree if it is connected and has no circuits.
Q. Are the previous two graphs trees?
Properties of trees:
In a tree there is one and only one path between every
pair of vertices (nodes)
A tree with n vertices has n-1 edges
A leaf in a tree can be defined as a vertex of degree one
Vertices other than leaves are called internal vertices
Formal Language 22
Theory
Graphs and trees: cont’d
Formal Language 23
Theory
Graphs and trees: cont’d
1
Ex. 1. List the leaves.
3 2. List the internal nodes.
2
3. What is the length of the
path from 1 to 9?
10 4 5 6
4. What is the height of the
tree?
7 8
Formal Language 24
Theory
Strings and languages
Strings
An alphabet, ∑, is a set of finite symbols.
A string over an alphabet ∑ is a sequence of symbols from ∑.
An empty string is a string without symbols, and is denoted by λ.
Ex. ∑ = {0, 1} => ∑* = {λ, 0, 1, 01, 00, 11, 111, 0101, 0000, …}
∑i is a set of strings of length i, i = 0, 1, 2, …
*
Let x Є ∑ and /x/ = n, then x = a1a2…an, ai Є ∑
Formal Language 25
Theory
Strings and languages: cont’d
Operations on strings
Concatenation operation
Let x, y Є ∑* and /x/ = n and /y/ = m. Then xy,
concatenation of x and y, = a1a2…anb1b2…bm, ai, bi Є ∑
The set ∑* has an identity element λ with respect to the
binary operation of concatenation.
Ex. x Є ∑* , xλ = λx = x
∑* has left and right cancellation
For x, y, z Є ∑*,
zx = zy => x = y (left cancellation)
xz = yz => x = y (right cancellation)
For x, y Є ∑* , we have /xy/ = /x/ + /y/
Formal Language 26
Theory
Strings and languages: cont’d
Transpose operation
For any x in ∑* and a in ∑, (xa)T = a(x)T
Ex. (aaabab)T = babaaa
A palindrome of even length can be obtained by the
concatenation of a string and its transpose.
A prefix of a string is a substring of leading symbols of
that string.
w is a prefix of y if there exists y’ in ∑* such that y=wy’
Ex. y = 123, list all prefixes of y.
A suffix of a string is a substring of trailing symbols of that
string.
w is a prefix of y if there exists y’ in ∑* such that y=y’w
Ex. y = 123, list all suffixes of y.
Formal Language 27
Theory
Strings and languages: cont’d
Formal Language 28
Theory
Strings and languages: cont’d
Languages
Definition: A language, L, is a set (collection) of strings over a given
alphabet, ∑.
A string in L is called a sentence or word.
Ex. ∑ = {0, 1}, ∑* = {λ, 0, 1, 01, 00, 11, …}
L1 = {λ}, L2 = {0, 1, 01} over ∑
L3 = {an | n>= 0} over ∑ = {a}
Formal Language 29
Theory
! !
ND ??
E N
IO
ST
E