[PDF] Regular Expressions

◇Regular expressions are an algebraic ◇If E is a regular expression, then L(E ) is the language it defines ε is the identity for concatenation ◇ εR = Rε = R

CS 360 Naomi Nishimura Regular expression identities 1 L + M = M + L 2 (L + M) + N = L + (M + N) 3 (LM)N = L(MN) 4 ∅ + L = L + ∅ = L 5 ϵL = Lϵ = L 6

[PDF] Regular Expression Identities - JFLAP

Applying the regular expression identity, (uv)*u = u(vu)*, this regular expression may be re-‐written as WSL(RSL)*R To do so, we will create each regular expression separately and convert each to an NFA, then to a DFA Once both DFAs are created, we can then compare the DFAs and check for equivalence

[PDF] Exercise 2 - JFLAP

Your textbook may have a section in it describing various regular expression identities To show formally that two regular expressions are equivalent, we must

[PDF] Closure Properties of Regular Languages

Like arithmetic expressions, the regular expressions have a number of laws that An identity for an operator is a value that when the operator is applied to the

[PDF] Regular Expressions - Stanford InfoLab

◇Regular expressions are an algebraic ◇If E is a regular expression, then L(E ) is the language it defines ε is the identity for concatenation ◇ εR = Rε = R

Regular expressions can be seen as a system of notations for denoting ϵ-NFA They form an Each regular expression E represents also a language L(E)

[PDF] Regular Expressions Regular Expressions

We can define an algebra for regular expressions (R) where R is a regular expression, then a parenthesized R is The identity for concatenation is: – Lε = εL

[PDF] Regular Expressions - CS 373: Theory of Computation - University

Definition and Identities Regular Expressions and Regular Languages Regular Expressions to NFA Regular Expressions A Simple Programming Language

[PDF] Regular Expressions - Computer Science - University of Colorado

The third equality holds as ε is identity for concatenation, while the last equality follows from (L∗)∗ = L∗ Ashutosh Trivedi Lecture 3: Regular Expressions Page

Regular Expressions

Definitions

Equivalence to Finite Automata

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 ais 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 E

1 and E 2 are regular expressions, then E 1 +E 2 is a regular expression, and L(E 1 +E 2 L(E 1 )L(E 2

Induction 2: If E

1 and E 2 are regular expressions, then E 1 E 2 is a regular expression, and L(E 1 E 2 ) = L(E 1 )L(E 2

Concatenation

: the set of strings wx such that w

Is in L(E

1 ) and x is in L(E 2 5

RE's: Definition - (3)

Induction 3: If E is a RE, then E* is a

RE, and L(E) = (L(E)).

Closure

, or "Kleene closure" = set of strings w 1 w 2 ...w n , for some n >

0, where each w

i is in L(E).

Note: when n=0, the string is ˝.

Precedence of Operators

Parentheses may be used wherever

needed to influence the grouping of operators.

Order of precedence is * (highest),

then concatenation, then + (lowest). 7

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. 8

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.

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). 10

Form of ˝-NFA's Constructed

No arcs from outside,

no arcs leaving

Start state:

Only state

with external predecessors"Final" state:

Only state

with external successors 11

RE to ˝-NFA: Basis

Symbol a:

a˝ 12

RE to ˝-NFA: Induction 1- Union

For E 1 For E 2 For E 1 E 2 13

RE to ˝-NFA: Induction 2-

Concatenation

For E 1 For E 2 For E 1 E 2 14

RE to ˝-NFA: Induction 3- Closure

For E

For E*

DFA-to-RE

A strange sort of induction.

States of the DFA are assumed to be

1,2,...,n.

We construct RE's for the labels of

restricted sets of paths.

Basis: single arcs or no arc at all.

Induction: paths that are allowed to

traverse next state in order. 16 k-Paths

A k-path is a path through the graph of

the DFA that goes thoughno state numbered higher than k.

Endpoints are not restricted; they can

be any state. 17

Example: k-Paths

1 3 2 0001 1

10-paths from 2 to 3:

RE for labels = 0.

1-paths from 2 to 3:

RE for labels = 0+11.

2-paths from 2 to 3:

RE for labels =

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

3-paths from 2 to 3:

RE for labels = ??

18 k-Path Induction Let R ijk be the regular expression for the set of labels of k-paths from state i to state j.

Basis: k=0. R

ij0 = sum of labels of arc from i to j. if no such arc.

But add ˝if i=j.

Example: Basis

R 120
= 0. R 110
1 3 2 0001 1 1 20 k-Path Inductive Case

A k-path from i to j either:

1.Never goes through state k, or

2.Goes through k one or more times.

R ijkquotesdbs_dbs17.pdfusesText_23

[PDF] [PDF] Regular Expressions - Stanford InfoLab

Regular Expressions

Definitions

Equivalence to Finite Automata

RE's: Introduction

Regular expressions

They describe exactly the regular

If E is a regular expression, then L(E) is

We'll describe RE's and their languages

RE's: Definition

Basis 1: If

RE, and L(a) = {a}.

Note: {a} is the language containing one

Basis 2: ˝is a RE, and L(˝) = {˝}.

Basis 3:

RE's: Definition - (2)

Induction 1: If E

Induction 2: If E

Concatenation

Is in L(E

RE's: Definition - (3)

Induction 3: If E is a RE, then E* is a

RE, and L(E*) = (L(E))*.

Closure

0, where each w

Note: when n=0, the string is ˝.

Precedence of Operators

Parentheses may be used wherever

Order of precedence is * (highest),

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

Equivalence of RE's and

Automata

We need to show that for every RE,

Pick the most powerful automaton type: the

˝-NFA.

And we need to show that for every

Pick the most restrictive type: the DFA.

Converting a RE to an ˝-NFA

Proof is an induction on the number of

We always construct an automaton of a

Form of ˝-NFA's Constructed

No arcs from outside,

Start state:

Only state

Only state

RE to ˝-NFA: Basis

Symbol a:

RE to ˝-NFA: Induction 1- Union

RE to ˝-NFA: Induction 2-

Concatenation

RE to ˝-NFA: Induction 3- Closure

For E*

DFA-to-RE

A strange sort of induction.

States of the DFA are assumed to be

1,2,...,n.

We construct RE's for the labels of

Basis: single arcs or no arc at all.

Induction: paths that are allowed to

A k-path is a path through the graph of

Endpoints are not restricted; they can

Example: k-Paths

10-paths from 2 to 3:

RE for labels = 0.

1-paths from 2 to 3:

RE for labels = 0+11.

2-paths from 2 to 3:

RE for labels =

3-paths from 2 to 3:

RE for labels = ??

Basis: k=0. R

But add ˝if i=j.

Example: Basis

A k-path from i to j either:

RE, and L(E) = (L(E)).