Regular expressions and languages pdf

Also since {a} is regular, {a}* is a regular language which is the set of strings consisting of a's such as , a, aa, aaa, aaaa etc. Note also that *, which is the set of strings consisting of a's and b's, is a regular language because {a, b} is regular. Regular expressions are used to denote regular languages.

1. Topic - Regular Expressions and Topic - Regular Expressions and
LanguagesLanguages
Dilouar Hossain
[email protected]

2. Topic ContentsTopic Contents
 Regular ExpressionsRegular Expressions

 Finite Automata and Regular ExpressionsFinite Automata and Regular Expressions

 Applications of Regular ExpressionsApplications of Regular Expressions

 Algebraic Laws for Regular ExpressionsAlgebraic Laws for Regular Expressions


3. Regular Expressions
Md. Tarek Habib3
Regular expressions are language-defining notation
Regular expressions are useful in applications such as text-search
applications and compiler components

4. Regular Expressions…
Md. Tarek Habib4
A FA (NFA or DFA) is a “blueprint" for constructing
a machine recognizing regular language.
A regular expression is a “user-friendly,"
declarative way of describing a regular language.
Example: 01* + 10*
Regular expressions are used in
1. UNIX grep command
2. UNIX Lex (Lexical analyzer generator)
.
.
.

5. Operations
5

6. Building Regular Expressions (regex’s)
6

7. Example
7

8. Equivalence of FA’s and regex’s
Md. Tarek Habib8

9. FA to regex
9
For each accepting state q, apply a reduction process to
produce an equivalent automaton with regular-
expression labels on the arcs. Eliminate all states except
q and the start state q
0
.
If q ≠ q
0
, then we shall be left with a two-state
automaton that looks like:

10. FA to regex…
Md. Tarek Habib10
If the start state is also an accepting state, then we must
also perform a state-elimination from the original FA
that gets rid of every state except the start state. Then
we are left with a one-state automaton:

11. FA to regex…
Md. Tarek Habib11
If there is more than one final state in the original FA, then
we must union all the Eq to obtain the final regular
expression.

12. FA to regex Example
Md. Tarek Habib12

13. FA to regex Example…
13

14. FA to regex Example…
14

15. regex to FA
Md. Tarek Habib15
Suppose L = L(R) for a regex R. Then we can design a -NFA
ε
E such that L(R) = L(E).
E will have:
•Exactly one accepting state
•No arcs into the initial state
•No arcs out of the accepting state

16. regex to FA…
Md. Tarek Habib16

17. regex to FA…
17

18. regex to FA Example
18

19. Algebraic Laws for Regular Expressions:
Commutativity and Associativity
Md. Tarek Habib19

20. Algebraic Laws for Regular Expressions:
Identities and Annihilators
Md. Tarek Habib20

21. Algebraic Laws for Regular Expressions:
Distributive Laws
Md. Tarek Habib21

22. Algebraic Laws for Regular Expressions:
Distributive Laws
Md. Tarek Habib22

23. Algebraic Laws for Regular Expressions:
The Idempotent Law
Md. Tarek Habib23

24. Algebraic Laws for Regular Expressions:
Laws Involving Closures
Md. Tarek Habib24

25. The End