Formal Languages & Finite Theory of Automata: BS Course
Formal Languages & Finite Theory of Automata: BS Course
Formal Languages & Finite Theory of Automata: BS Course
Theory of Automata
BS Course
Slide # : 04
Muhammad Faizan Tahir
Regular Expressions
Definitions
Equivalence to Finite Automata
2
RE’s: Introduction
Regular expressions are an algebraic
way to describe languages.
They describe exactly the regular
languages.
If E is a regular expression, then L(E) is
the language it defines.
We’ll describe RE’s and their languages
recursively.
3
RE’s: Definition
Basis 1: If a is any symbol, then a is a
RE, and L(a) = {a}.
Note: {a} is the language containing one
string, and that string is of length 1.
Basis 2: ε is a RE, and L(ε) = {ε}.
Basis 3: ∅ is a RE, and L(∅) = ∅.
4
RE’s: Definition – (2)
Induction 1: If E1 and E2 are regular
expressions, then E1+E2 is also a
regular expression, and L(E1+E2) =
L(E1)L(E2).
Induction 2: If E1 and E2 are regular
expressions, then E1E2 is also a regular
expression, and L(E1E2) = L(E1)L(E2).
Concatenation : the set of strings wx such that w
Is in L(E1) and x is in L(E2). 5
RE’s: Definition – (3)
Induction 3: If E is a RE, then E* is a
RE, and L(E*) = (L(E))*.
6
Definition (continued)
For regular expressions r1 and r2
L r1 r2 L r1 L r2
L r1 r2 L r1 L r2
L r1 * L r1 *
L r1 L r1
7
Precedence of Operators
Parentheses may be used wherever
needed to influence the grouping of
operators.
Order of precedence is * (highest), then
concatenation, then + (lowest).
8
Examples: RE’s
L(01) = {01}.
L(01+0) = {01, 0}.
L(0(1+0)) = {01, 00}.
Note order of precedence of operators.
L(0*) = {ε, 0, 00, 000,… }.
L((0+10)*(ε+1)) = all strings of 0’s
and 1’s without two consecutive 1’s.
9
Regular Expressions
Regular expressions
describe regular languages
(a b c) *
Example:
describes the language
a, bc* , a, bc, aa, abc, bca,...
Example
Regular expression: a b a *
L a b a * L a b L a *
L a b L a *
L a L b L a *
a b a *
a, b , a, aa, aaa,...
a, aa, aaa,..., b, ba, baa,... 11
Example
Regular expression r a b * a bb
12
Example
Regular expression r aa * bb * b
L r {a b
2n 2m
b : n, m 0}
13
Example
Regular expression r (0 1) * 00 (0 1) *
14
Example
15
Examples
Describe the following REs in English.
language.
- 10*1
- a*b*
- (ab)*
- (a* + b*)c*
- (00)*(11)*1
- a(a+b)*abb
Examples
Build Regular Expression of the following:
- An RE consists of any combination of a and b,
beginning with a and ending with b.
- A language of any combination of a and b containing
aab as a substring.
- RE of a and b containing at least 2 a’s.
- Write an RE for the languages L = {an bm|where m+n
is even.
- An RE of a and b, having exactly one a.
Examples
- L1 = a(a + b)*b
-L2 = (a + b)*abb (a + b)*
-L3 = (a + b)*a (a + b)*a (a + b)*
-L4 = (aa)*(bb)* + (aa)*a(bb)*b
-L5 = b*ab*
Equivalence of RE’s and
Automata
We need to show that for every RE,
there is an automaton that accepts the
same language.
Pick the most powerful automaton type: the
ε-NFA.
And we need to show that for every
automaton, there is a RE defining its
language.
Pick the most restrictive type: the DFA. 19
Converting a RE to an ε-NFA
Proof is an induction on the number of
operators (+, concatenation, *) in the
RE.
We always construct an automaton of a
special form (next slide).
20
Form of ε-NFA’s Constructed
21
RE to ε-NFA: Basis
a
Symbol a:
ε: ε
∅:
22
RE to ε-NFA: Induction 1 – Union
P+Q P
23
RE to ε-NFA: Induction 2 –
Concatenation
P.Q P Q
24
RE to ε-NFA: Induction 3 – Closure
P* € €
€ = Null Value
25
Examples (RE to FA)
L = ab*c
L = (a + b)c
L = a(bc)*
L = (a + b)* (aa + bb) (a + b)*
L = ab (aa + bb) (a + b)* b
L = ab + (aa + bb)* b
Arden's Theorem
In order to find out a regular expression of a
Finite Automaton, we use Arden’s Theorem
along with the properties of regular
expressions.
Statement −
Let P and Q be two regular expressions.
If P does not contain null string,
then R = Q + RP has a unique solution that
is R = QP*
27
Arden's Theorem
Proof
R = Q + (Q + RP)P [After putting the value R = Q + RP]
R= Q + QP + RPP
When we put the value of R recursively again
and again, we get the following equation
R = Q + QP + QP2 + QP3…..
R = Q (ε + P + P2 + P3 + …. )
R = QP* [As P* represents (ε + P + P2 + P3 + ….) ]
28
Algebraic Laws for RE’s
Union and concatenation behave sort of
like addition and multiplication.
+ is commutative and associative;
concatenation is associative.
Concatenation distributes over +.
Exception: Concatenation is not
commutative.
29
Identities and Annihilators
∅ is the identity for +.
R+ ∅ = R.
ε is the identity for concatenation.
εR = Rε = R.
∅ is the annihilator for concatenation.
∅R = R∅ = ∅.
30
The Pumping Lemma
We have, almost accidentally, proved a
statement that is quite useful for showing
certain languages are not regular.
Called the pumping lemma for regular
languages.
31
Statement of the Pumping Lemma
Number of
For every regular language L states of
DFA for L
There is an integer p, such that
For every string w in L of length > p
We can write w = xyz such that:
1. |xy| < p.
Labels along
2. |y| > 0. first cycle on
3. For all i > 0, xyiz is in L. path labeled w
32
Example: Use of Pumping Lemma
We have claimed {0n1n | n > 1} is not a
regular language.
Suppose it were. Then there would be
an associated n for the pumping lemma.
Let w = 0p1p. We can write w = xyz,
where x and y consist of 0’s, and y ε.
But then xyyz would be in L, and this
string has more 0’s than 1’s.
33