[go: up one dir, main page]
Scribd
Upload
986 views25 pages

Chapter 3 Regular Expression

Regular expressions were designed to represent regular languages using primitives like symbols, parentheses, and operators. A regular expression combines strings from an alphabet using operations like union, concatenation, and Kleene star. Regular expressions can be used to define regular languages and can be represented by nondeterministic finite automata through operations on the regular expressions. The pumping lemma can be used to prove that a language is not regular by finding a contradiction for any string of length greater than the pumping length c.

Uploaded by

mimisbhatu
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
986 views25 pages

Chapter 3 Regular Expression

Regular expressions were designed to represent regular languages using primitives like symbols, parentheses, and operators. A regular expression combines strings from an alphabet using operations like union, concatenation, and Kleene star. Regular expressions can be used to define regular languages and can be represented by nondeterministic finite automata through operations on the regular expressions. The pumping lemma can be used to prove that a language is not regular by finding a contradiction for any string of length greater than the pumping length c.

Uploaded by

mimisbhatu
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 25

Chapter-3

REGULAR EXPRESSION
Regular Expressions

Regular expressions were designed to represent regular languages

A mathematical tool built from a set of primitives and operations.

Combines strings of symbols from some alphabet Σ, parentheses


and the operators +, ⋅, and *.

A regular expression is obtained from the symbol {a, b, c}, empty


string ∈, and empty-set ∅ perform the operations +, ⋅ and *
(union, concatenation and Kleene star).
Regular Expressions

Examples
0 + 1 represents the set {0, 1}
1 represents the set {1}
0 represents the set {0}
(0 +1)1 represents the set {01, 11}
(a+b)⋅(b+c) represents the set {ab, bb, ac, bc}
(0 + 1)* = ∈+ (0 + 1) + (0 + 1) (0 + 1)..........= Σ*
(0 + 1 )+ =(0 +1) (0 +1)*= Σ+ =Σ*- {ε}
Building Regular Expressions

Assume that Σ = {a,b,c}


Zero or more: a* means zero or more a’s,

To say zero or more ab’s, i.e.,{λ, ab,abab........,} you need to say (ab)*.

One or more: Since a* means zero or more a’s, you can use aa*
(or equivalently a*a) to mean one or more a’s.
Similarly to describe ‘one or more ab’s”, that is {ab, abab, ababab,
.........}, you can use ab (ab)*.

Zero or one: It can be described as an optional ‘a’ with (a + λ).


Languages defined by Regular Expressions
Regular Expressions to NFA

For any x in Σ, the regular expression denotes the language {x}.


The NFA (with a single start state and a single final state) as
shown below, represents exactly that language.

The regular expression λ denotes the language {λ}that is the


language containing only the empty string.
Regular Expressions to NFA

The regular expression ∅ denotes the language ∅; no


strings belong to this language, not even the empty
string.

For juxtaposition, strings in L(r1) followed by strings in L(r2) ,


we chain the NFAs together
Regular Expressions to NFA

The “+” denotes “or” in a regular expression, we would use an


NFA with a choice of paths.

The star (*) denotes zero or more applications of the regular


expression, hence a loop has to be set up in the NFA.
Example

Represent the following sets by regular expression


a. {∧, ab}
b. {1,11,111....}
c. {ab, a, b, bb}
Solution
a. The set {∧, ab} is represented by the regular expression ∧ + ab
b. The set{1, 11,111,....,}is got by concatenating 1 and any
element of {1}*.
Therefore 1(1)* represent the given set.
c. The set {ab, a, b, bb} represents the regular expression
ab+ a+ b +bb.
Exercise
1. Obtain the regular expressions for the following sets:
1.1. The set of all strings over {a, b} beginning and ending with
‘a’.
 The regular expression for ‘the set of all strings over {a, b}
beginning and ending with ‘a’ is given by: a (a + b)*a

1.2. {b2, b5, b8,. . . . .}


 The regular expression for {b 2 , b 5 , b 8 , ............} is given by:
bb (bbb)*

1.3. {a2n+1 |n > 0}


 The regular expression for {a n 2 1 n+ | > 0}is given by:

a (aa)*
FINITE AUTOMATA WITH OUTPUT

 A finite-state machine M = (Q , Σ, δ , λ, O , q0 ) consists of

 a finite set Q of states,


 a finite input alphabet Σ,
 a finite output alphabet O,
 a transition function δ that assigns to each state and input pair a
new state,
 an output function λ that assigns to each state and input pair an
output, and
 an initial state q0.
 There are two types of finite state machines that generate
output −
 Mealy Machine
 Moore Machine
 Mealy Machine
 A Mealy Machine is an FSM whose output depends on the
present state as well as the present input.
 It can be described by a 6 tuple (Q, ∑, O, δ, X, q0)
M = (Q , O , ,Σ , δ , λ , q0 ) consists of
a finite set Q of states,
a finite input alphabet Σ,
a finite output alphabet O,
a transition function δ that assigns
to each state and input pair a new
state,
an output function λ that assigns to
each state and input pair an output,
and an initial state q0.
Examples

The above Mealy Machine outputs a value for each input.


You can tell which is which by: input /output.
So for the following input:
000101010
It outputs
000010101
Moore Machine

 Moore machine is an FSM whose outputs depend on only the


present state.
 A Moore machine can be described by a 6 tuple(Q, ∑, O, δ, X, q0)
Regular Languages
 Regular Languages
Language accepted by a DFA.

 A language 𝐿 is regular if exists a DFA 𝐷 such


𝐿 = 𝐿(𝐷).
Regular Languages

 Let Σ be an alphabet. The class of “regular languages”

over Σ is defined inductively as follows:


a) ∅ is a regular language

b) For each σ ∈ Σ,{σ }is a regular language

c) For any natural number n ≥ 2, if L1, L2, L3, .... ,Ln


are regular languages, then so is L1∪L2 ∪......∪ Ln.
Regular Languages

d) For any natural number n ≥ 2, if L1 L2,...... Ln are

regular languages, then so is L1 L2 ...... Ln.

e) If L is a regular language, then so is L*.

(f) Nothing else is a regular language unless its

construction follows from rules (a) to (e).


Examples

i. ∅ is a regular language (by rule (a))

ii. L = {a, ab} is a language over Σ = {a, b}because, both {a}


and {b} are regular languages by rule (b).

{a} o {b}={ab} is a regular language. By rule (d)

{a }∪{ab } = L is a regular language. Using rule (c),

iii. The language over the alphabet {0,1} where strings contain
an even number of 0’s can be constructed by
(1*((01*)(01*))*) or simply 1*(01* 01*)*.
PROPERTIES OF REGULAR LANGUAGES

 A regular set (language) is a set accepted by a finite


automaton.
Closure

 A set is closed under an operation if, whenever the operation is


applied to members of the set, the result is also a member of
the set.
PROPERTIES OF REGULAR LANGUAGES

 There are several operations defined on languages:

L1 ∪ L2: strings in either L1 or L2.


L1 ∩ L2 : strings in both L1 and L2.
L1L2 : strings composed of one string from L, followed by one
string from L2.
L1*: Zero or more strings from L1 concatenated together
L1-L2 : strings in L1 that are not in L2.
L1R : strings in L1, reversed.
Applying the Pumping Lemma

Theorem
Let L be a regular language. Then there exists a constant ‘c’ such that
for every string w in L −
|w| ≥ c
We can break w into three strings,
w = xyz, such that −
|y| > 0
|xy| ≤ c
For all k ≥ 0, the string xykz is also in L.
 The “pumping lemma” for regular languages is another way of
showing that a given infinite language is not regular.
Applications of Pumping Lemma
 Method to prove that a language L is not regular

 At first, we have to assume that L is regular.

 So, the pumping lemma should hold for L.

 Use the pumping lemma to obtain a contradiction −

 Select w such that |w| ≥ c


 Select y such that |y| ≥ 1
 Select x such that |xy| ≤ c
 Assign the remaining string to z.
 Select k such that the resulting string is not in L.
 Hence L is not regular.
Problem

Prove that L = {aibi | i ≥ 0} is not regular.


Solution: At first, assume that L is regular and n is the number of states.
Let w = anbn. Thus |w| = 2n ≥ n.
By pumping lemma, let w = xyz, where |xy|≤ n.
Let x = ap, y = aq, and z = arbn, where p + q + r = n.
p ≠ 0, q ≠ 0, r ≠ 0. Thus |y|≠ 0
Let k = 2. Then xy2z = apa2qarbn.
Number of as = (p + 2q + r) = (p + q + r) + q = n + q
Hence, xy2z = an+q bn. Since q ≠ 0, xy2z is not of the form anbn.
Thus, xy2z is not in L. Hence L is not regular.
Complement of a DFA

 If (Q, ∑, δ, q0, F) be a DFA that accepts a language L, then the

complement of the DFA can be obtained by swapping its


accepting states with its non-accepting states and vice versa.

 We will take an example and elaborate this below −

This DFA accepts the language


L = {a, aa, aaa , ............. }
over the alphabet
∑ = {a, b}
So, RE = a+.
Con..

Now we will swap its accepting states with its non-accepting states
and vice versa and will get the following −

This DFA accepts the language


Ľ = { ε , b, ab ,bb,ba, ............... } over the alphabet
∑ = {a, b}

You might also like