Lecture Notes 4: Regular Expressions 1 Regular Expression PDF

Also [A-za-z0-9] [:digits:]

Lecture 18: Theory of Computation Regular Expressions and DFAs

Use Matcher data type to simulate NFA. ?. (NFA is fancy but equivalent variety of DFA) import java.util.regex.

Introduction to Theoretical CS Regular Expressions

Cryptography: theory of computational complexity. • Data compression: theory of information. “ In theory there is no difference between theory and practice. In

CS 373: Theory of Computation

?0 = Agha-Viswanathan. CS373. Page 27. Operations on Languages. Regular Expressions. Kleene Closure. Definition. Ln = (. {?} if n = 0. Ln?1 ? L otherwise.

10 Patterns Automata

http://infolab.stanford.edu/~ullman/focs/ch10.pdf

THEORY OF COMPUTATION LECTURE NOTES Bachelor of

Theory: Alphabets Strings Languages

Automata Theory and Applications

Why Study the Theory of Computation? PART II: FINITE STATE MACHINES AND REGULAR LANGUAGES . ... 6.3 Applications of Regular Expressions .

Explanations for Regular Expressions

context of formal language theory and a primary use has been as part of scanners in many applications of regular expressions involve the description of ...

REGULAR EXPRESSIONS AND AUTOMATA

The regular expression is used for specifying text strings in situations like this Web-search example and in other in- formation retrieval applications

Lecture Notes 4: Regular Expressions 1 Regular Expression

CS340: Theory of Computation. Sem I 2017-18. Lecture Notes 4: Regular Expressions. Raghunath Tewari. IIT Kanpur. 1 Regular Expression.

CS340: Theory of ComputationSem I 2017-18

Lecture Notes 4: Regular Expressions

Raghunath TewariIIT Kanpur1 Regular Expression

An algebraic w ayto represen tregular lan guages.

Some practical applications: pattern matc hingin text editors, used in compiler design.

Some examplesExpressionLanguage

0f0g1f1g0[1f0;1g0

Each expression corresponds to a language. Regular expressions are dened inductively as shown below. Denition 1.1.Ris said to be aregular expression(or RE in short) ifRhas one of the following forms:Regular ExpressionLanguage of the regular expression orL(R)Comment ;fgthe empty set fgthe set containingonlyafaga2R

1[R2L(R1)[L(R2)for two regular expressionsR1and

R 2R

1R2L(R1)L(R2)for two regular expressionsR1and

R 2R

1(L(R1))for a regular expressionR1(R1)L(R1)for a regular expressionR1Remark.Note the following

Regular expressions are w elldened. In other w ords,eac hregular expression corresp ondsto a unique language. Is the converse true? -[is often replaced by +. HenceR1[R2is the same asR1+R2.

The dot sym bolis often discarded.

() giv esprecedence to an expression (similar to standard arithmetic). -Order of pr ecedence(higher to lo wer):() [ The language corresp ondingto the RE ;isfg. (sinceis the concatenation of zero symbols from the set;)

Some more examples of REs and their corresponding languages.RL(R)01f01g01 + 1f01;1g(01 +)1f011;1g(0 + 10)

(+ 1)f;0;10;00;001;010;0101;:::gInformally,L(R) consists of all those strings that \matches" the regular expressionR. Let us see

some examples of the other type. That is given a regular language, what is the corresponding regular expression.LanguageRE fwjwhas a single 1g0

10fwjwhas at most a single 1g0

+ 010fwj jwjis a multiple of 3g((0 + 1)(0 + 1)(0 + 1)) fwjwhas a 1 at every odd position andjwjis oddg1((0 + 1)1) fwjwhas a 1 at every even positiong((0 + 1)1) + (0 + 1)(1(0 + 1))We say that two regular expressionsR1andR2are equivalent (denoted asR1=R2) if

L(R1) =L(R2).

Note 1.Some basic algebraic properties of REs.

1.R1+ (R2+R3) = (R1+R2) +R3

2.R1(R2R3) = (R1R2)R3

3.R1(R2+R3) =R1R2+R1R3

4. ( R1+R2)R3=R1R3+R2R3

5.R1+R2=R2+R1(only addition is commutative))

6. ( R)=R

7.R=R=R

8.R;=;R=;

9.R+;=R

2 Regular Expressions and Regular Languages

Theorem 1.A languageLis regular if and only ifL=L(R)for some regular expressionR. In other words, REs are equivalent in power to NFAs/DFAs.

2.1 Converting an RE to an NFA

Given a regular expression, we will convert it into an NFANsuch thatL(R) =L(N). We will give a case based analysis based on the inductive denition of REs.

Case 1:R=;. NFA isstart

Case 2:R=. NFA isstart

Case 3:R=afor somea2. NFA isstarta

Case 4:R=R1+R2, whereR1andR2are two REs. LetN1andN2be the NFAs forR1and R

2respectively. Then the NFA forRisqstartrq

1r 1N 1q 2r 2N 2 Case 5:R=R1R2, whereR1andR2are two REs. LetN1andN2be the NFAs forR1andR2 respectively. Then the NFA forRisqstartrq 1r 1N 1q 2r 2N 2 Case 6:R=R1, whereR1is an RE. LetN1be the NFA forR1. Then the NFA forRisqstartrq 1r 1N 1 The above construction constructs an NFA from an RE in an inductive manner. Therefore the class of languages accepted by regular expressions are a subset of regular languages.

2.2 Generalized Nondeterministic Finite Automaton

We will now prove that for every regular language there exists a regular expression. For this we will introduce another type of nite automaton known asgeneralized non-deterministic nite automaton(or GNFA). A GNFA is a non-deterministic automaton with transitions being labeled with regular expressions instead of just symbols from the alphabet or. Here is an example of a GNFA.q startstartq 2q 1q accept;01 00 11

10 + 01

0(11) 1

Strings accepted by the above GNFA:

01101 : in m ultiplew ays.

00 : at least 3 w ays.

0100

Strings not accepted by the above GNFA:

-10 : no w ayto partition so that it matc hesa sequence from start to accept state A stringw2is accepted by a GNFA ifw=w1w2:::wk, where eachwi2and there exists a sequence of statesq0;q1;:::qk, such that -q0is the start state, -qkis the accept state, and for eac hi, if the transition fromqi1toqiis labeled with the regular expressionRi, then w i2L(Ri). We assume the following conditions on a GNFA without loss of generality. 1. Has a unique start state and a unique acc eptstate. 2. The start state has a transition going out to ev eryother state (excluding itself ). 3. No transition coming in tothe start state from an yother s tate. 4. The acce ptstate has a transition coming in from ev eryoth erstate (excluding itse lf). 5. No transition goin gout of the accept state to an yother state. 6. Except for the start and ac ceptstates, there are transitions b etweenev erypair of states (in both directions), and also from a state to itself.

2.3 Converting a DFA to an RE

We will illustrate the algorithm with an example.

Consider the follo wingDF A.1start

32a;ba

bb a 2. W econ vertthe DF Ain toa GNF Asatisfying the ab oveas sumptions. Create new start state sand new start accepting statet. Let the new set of states beQ

Add transition fromsto old start state.

Add transitions from old accept states tot.

-Mak esure there are transition sfrom sto every state in the GNFA (exceptsitself), and from every state (exceptt) tot. Add transitions f romev erystate in Qn fs;tgto every other state inQn fs;tg, putting the label;, if a transition did not exist there earlier.1

32sstartt

;a+b ;a b;; b a; 3. W eno wremo vestates in Qn fs;tg, one at a time. replace the resulting transitions with suitable labels as described below. Consider the following set of 3 states with regular expressions labeled on the transitions, andqripis the state that we want to remove.q iq ripq jR 1R 2R 3R

4Then on removingqrip, the resulting GNFA will beq

iq jR

1+R2R3R4-GNF Aafter remo vingstate 1.

sstart2 3t ;a+b a b; b+a(a+b)+a;

GNF Aafter remo vingstate 2.sstart3t

(a+b)ab(b+a(a+b))ab+a-GNF Aafter remo vingstate 3.sstartt+ ((a+b)ab)((b+a(a+b))ab)(+a)Therefore regular expression corresponding to the given DFA is

+ ((a+b)ab)((b+a(a+b))ab)(+a)quotesdbs_dbs17.pdfusesText_23

[PDF] Lecture Notes 4: Regular Expressions 1 Regular Expression