1 of 17

9/9/2024

Sri Raghavendra Educational Institutions Society (R)

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

www.skit.org.in

Department of Computer Science & Engineering

SUBJECT CODE:BCS503

SUBJECT NAME:THEORY OF COMPUTATION

2 of 17

Regular Expressions

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

3 of 17

Regular Expressions vs. Finite Automata

Offers a declarative way to express the pattern of any string we want to accept

E.g., 01*+ 10*

Automata => more machine-like

< input: string , output: [accept/reject] >

Regular expressions => more program syntax-like

Unix environments heavily use regular expressions

E.g., bash shell, grep, vi & other editors, sed

Perl scripting – good for string processing
Lexical analyzers such as Lex or Flex

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

4 of 17

Regular Expressions

Regular �expressions

Finite Automata�(DFA, NFA, ε-NFA)

Regular�Languages

Automata/machines

Syntactical �expressions

Formal language �classes

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

5 of 17

Language Operators

Union of two languages:

L U M = all strings that are either in L or M
Note: A union of two languages produces a third language

Concatenation of two languages:

L . M = all strings that are of the form xy � s.t., x ∈ L and y ∈ M
The dot operator is usually omitted

i.e., LM is same as L.M

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

6 of 17

Kleene Closure (the * operator)

Kleene Closure of a given language L:

L⁰= {ε}
L¹= {w | for some w ∈ L}
L²= { w₁w₂| w₁ ∈ L, w₂ ∈ L (duplicates allowed)}
Lⁱ= { w₁w₂…w_i| all w’s chosen are ∈ L (duplicates allowed)}
(Note: the choice of each w_i is independent)
L* = U_i≥0 Lⁱ (arbitrary number of concatenations)

Example:

Let L = { 1, 00}

L⁰= {ε}
L¹= {1,00}
L²= {11,100,001,0000}
L³= {111,1100,1001,10000,000000,00001,00100,0011}
L* = L⁰ U L¹ U L² U …

“i” here refers to how many strings to concatenate from the parent language L to produce strings in the language Lⁱ

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

7 of 17

Kleene Closure (special notes)

L* is an infinite set iff |L|≥1 and L≠{ε}
If L={ε}, then L* = {ε}
If L = Φ, then L* = {ε}

Σ* denotes the set of all words over an alphabet Σ

Therefore, an abbreviated way of saying there is an arbitrary language L over an alphabet Σ is:

L ⊆ Σ*

Why?

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

8 of 17

Building Regular Expressions

Let E be a regular expression and the language represented by E is L(E)
Then:

(E) = E
L(E + F) = L(E) U L(F)
L(E F) = L(E) L(F)
L(E*) = (L(E))*

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

9 of 17

Example: how to use these regular expression properties and language operators?

L = { w | w is a binary string which does not contain two consecutive 0s or two consecutive 1s anywhere)

E.g., w = 01010101 is in L, while w = 10010 is not in L

Goal: Build a regular expression for L
Four cases for w:

Case A: w starts with 0 and |w| is even
Case B: w starts with 1 and |w| is even
Case C: w starts with 0 and |w| is odd
Case D: w starts with 1 and |w| is odd

Regular expression for the four cases:

Case A: (01)*
Case B: (10)*
Case C: 0(10)*
Case D: 1(01)*

Since L is the union of all 4 cases:

Reg Exp for L = (01)* + (10)* + 0(10)* + 1(01)*

If we introduce ε then the regular expression can be simplified to:

Reg Exp for L = (ε +1)(01)*(ε +0)

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

10 of 17

Precedence of Operators

Highest to lowest

* operator (star)
. (concatenation)
+ operator

Example:

01* + 1 = ( 0 . ((1)*) ) + 1

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

11 of 17

Finite Automata (FA) & Regular Expressions (Reg Ex)

To show that they are interchangeable, consider the following theorems:

Theorem 1: For every DFA A there exists a regular expression R such that L(R)=L(A)
Theorem 2: For every regular expression R there exists an ε -NFA E such that L(E)=L(R)

ε -NFA

NFA

DFA

Reg Ex

Theorem 2

Theorem 1

Proofs �in the book

Kleene Theorem

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

12 of 17

DFA to RE construction

Reg Ex

DFA

Theorem 1

Example:

q₀

q₁

q₂

0,1

(1*)

(0*)

(0 + 1)*

Informally, trace all distinct paths (traversing cycles only once) � from the start state to each of the final states � and enumerate all the expressions along the way

1*00*1(0+1)*

00*

(0+1)*

Q) What is the language?

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

13 of 17

RE to ε-NFA construction

ε -NFA

Reg Ex

Theorem 2

Example:

(0+1)*01(0+1)*

(0+1)*

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

14 of 17

Algebraic Laws of Regular Expressions

Commutative:

E+F = F+E

Associative:

(E+F)+G = E+(F+G)
(EF)G = E(FG)

Identity:

E+Φ = E
ε E = E ε = E

Annihilator:

ΦE = EΦ = Φ

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

15 of 17

Algebraic Laws…

Distributive:

E(F+G) = EF + EG
(F+G)E = FE+GE

Idempotent: E + E = E
Involving Kleene closures:

(E*)* = E*
Φ* = ε
ε* = ε
E⁺=EE*
E? = ε +E

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

16 of 17

True or False?

Let R and S be two regular expressions. Then:

((R*)*)* = R* ?

(R+S)* = R* + S* ?

(RS + R)* RS = (RR*S)* ?

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

17 of 17

Summary

Regular expressions
Equivalence to finite automata
DFA to regular expression conversion
Regular expression to ε-NFA conversion
Algebraic laws of regular expressions
Unix regular expressions and Lexical Analyzer

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in