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

[PDF] Regular Expressions and Converting an RE to a DFAJP - JFLAP

Nondeterministic Finite Automata Conversion of NFA to DFA Regular Languages Set Theory JFLAP Tutorial Description of Regular Expressions Regular 

[PDF] Convert Regular Expression to DFA - JFLAP

Convert Regular Expression to DFA -‐ Exercise Problem: Convert a(b+c)*a to a DFA The string must start with an a which is followed by a mix of b's and

[PDF] CS 301 - Lecture 3 NFA DFA Equivalence Regular Expressions

Could This Produce Infinite States? Powerset of finite set can be big, but it is not infinite There are a finite number of NFA states by definition 

[PDF] From regular expressions to DFAs using compressed NFAs - CORE

There are two principal methods for turning regular expressions into NFA's - one due to McNaughton Thompson's algorithm [24], and are believed to outperform Thompson's NFA's for II, Programmer's Manual, SUN microsystems, 1989

[PDF] Formal Languages, Automata and Computation DFAs to Regular

Generalized transitions: label transitions with regular expressions Generalized NFAs In fact, all standard DFA transitions are generalized transitions with example above) (CARNEGIE Lectures/2005-slides/lec09 pdf Introduction to 

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

Kleene's regular expressions, also appeared as Type-3 languages in Chomsky's hierarchy expressions: – ls lecture* pdf Regular Expressions: Examples Find regular Can we construct a DFA/NFA for a regular expression? Ashutosh  

[PDF] NFA to DFA conversion and regular expressions - CUHK CSE

Every NFA is equivalent to some DFA for the same language NFA → DFA example NFA: q0 q1 Will focus on regular expressions in formal language theory

[PDF] NFAs and regular expressions - MIT OpenCourseWare

Nondeterministic Finite Automata and the languages they recognize Regular expressions denote FA-recognizable languages Formal Definition of an NFA

[PDF] Converting a DFA to a Regular ExpressionJP

Conversion of Regular Expression to Deterministic Finite Automata Set Theory JFLAP Tutorial In this unit, we will look at the process of converting a DFA into 

[PDF] regular expression to dfa questions

[PDF] regular expression to grammar converter

[PDF] regular expression to nfa in c

[PDF] regular graph

[PDF] regular language closed under concatenation

[PDF] regular language to regular grammar

[PDF] regular octagonal prism volume

[PDF] regular overtime

[PDF] regular solution

[PDF] regular solution model

[PDF] regular solution model interaction parameter

[PDF] regular solution theory equation

[PDF] regular verb in pdf

[PDF] regular verbs list pdf

[PDF] regularization and optimization

Ashutosh Trivedi { 1 of 21CSCI 3434: Theory of Computation

Lecture 4: Regular Expressions

Ashutosh Trivedis

1starts

2s 3s

40;110;"10;1Department of Computer Science

University of Colorado Boulder

Ashutosh TrivediLecture 3: Regular Expressions

Ashutosh Trivedi { 2 of 21What are Regular Languages?

An alphab et = fa;b;cgis anite set of letters,

The set of all

strings (ak a,w ords) over an alphabet can be recursively dened as: as :

Base case: "2(empty string),

Indu ction:If w2thenwa2for alla2.

A language Lover somealphab et is a set of strings , i.e.L.

Some exam ples:

{Leven=fw2:wis of even lengthg {Lab=fw2:wis of the formanbmforn;m0g {Lanbn=fw2:wis of the formanbnforn0g {Lprime=fw2:whas a prime number ofa0sg

Deterministic nite state automata

dene languages that require nite resources (states) to recognize.Denition (Regular Languages)

We call a language

regula r if it can b e accepted b ya deterministic nite state automaton.

Ashutosh TrivediLecture 3: Regular Expressions

Ashutosh Trivedi { 2 of 21What are Regular Languages?

An alphab et = fa;b;cgis anite set of letters,

The set of all

strings (ak a,w ords) over an alphabet can be recursively dened as: as :

Base case: "2(empty string),

Indu ction:If w2thenwa2for alla2.

A language Lover somealphab et is a set of strings , i.e.L.

Some exam ples:

{Leven=fw2:wis of even lengthg {Lab=fw2:wis of the formanbmforn;m0g {Lanbn=fw2:wis of the formanbnforn0g {Lprime=fw2:whas a prime number ofa0sg

Deterministic nite state automata

dene languages that require nite resources (states) to recognize.Denition (Regular Languages)

We call a language

regula r if it can b e accepted b ya deterministic nite state automaton.

Ashutosh TrivediLecture 3: Regular Expressions

Ashutosh Trivedi { 3 of 21Why they are \Regular"

A numb erof widely dierent and equi-exp ressivefo rmalismsp recisely capture the same class of languages:

Deterministic nite state automata

Nondetermin isticnite state automata (also with "-transitions)

Klee ne's

regula rexp ressions , also appeared as

T ype-3langu ages

in

Chomsky's hierarchy [Cho59].

Monadic second-o rderlogic

denable languages [B

60, Elg61, Tra62]

Certain Algeb raicconnection (acceptabilit yvia nite semi-group) [RS59] We have already seen that: Theorem (DFA=NFA="-NFA)A language is accepted by adeterministic nite automaton if and only if it is accepted by a non-deterministic nite automaton .In this lecture we introduceRegula rExp ressions, and prove:

Theorem (REGEX=DFA)

A language is accepted by a

deterministic nite automaton if and only if it is accepted by a regula rexp ression

Ashutosh TrivediLecture 3: Regular Expressions

Ashutosh Trivedi { 3 of 21Why they are \Regular"

A numb erof widely dierent and equi-exp ressivefo rmalismsp recisely capture the same class of languages:

Deterministic nite state automata

Nondetermin isticnite state automata (also with "-transitions)

Klee ne's

regula rexp ressions , also appeared as

T ype-3langu ages

in

Chomsky's hierarchy [Cho59].

Monadic second-o rderlogic

denable languages [B

60, Elg61, Tra62]

Certain Algeb raicconnection (acceptabilit yvia nite semi-group) [RS59] We have already seen that: Theorem (DFA=NFA="-NFA)A language is accepted by adeterministic nite automaton if and only if it is accepted by a non-deterministic nite automaton .In this lecture we introduceRegula rExp ressions, and prove:

Theorem (REGEX=DFA)

A language is accepted by a

deterministic nite automaton if and only if it is accepted by a regula rexp ression

Ashutosh TrivediLecture 3: Regular Expressions

Ashutosh Trivedi { 3 of 21Why they are \Regular"

A numb erof widely dierent and equi-exp ressivefo rmalismsp recisely capture the same class of languages:

Deterministic nite state automata

Nondetermin isticnite state automata (also with "-transitions)

Klee ne's

regula rexp ressions , also appeared as

T ype-3langu ages

in

Chomsky's hierarchy [Cho59].

Monadic second-o rderlogic

denable languages [B

60, Elg61, Tra62]

Certain Algeb raicconnection (acceptabilit yvia nite semi-group) [RS59] We have already seen that: Theorem (DFA=NFA="-NFA)A language is accepted by adeterministic nite automaton if and only if it is accepted by a non-deterministic nite automaton .In this lecture we introduceRegula rExp ressions, and prove:

Theorem (REGEX=DFA)

A language is accepted by a

deterministic nite automaton if and only if it is accepted by a regula rexp ression

Ashutosh TrivediLecture 3: Regular Expressions

Ashutosh Trivedi { 4 of 21Regular Expressions (RegEx) textual ( declarative ) way to represent regular languages (compare automata) Users of UNIX-based systems will already b efamilia rwith these expressions: {ls lecture*.pdf {rm -rf *.* {grep automat* /usr/share/dict/words

Also used in A WK,exp r,Emacs and vi sea rches,

Lexi calanalysis t oolsli ke

exuse it for deningtok ens{Some useful String-set op erations: uni onL[Mdef=fw:w2Lorw2Mg concatenation L:Mdef=fu:v:u2Landv2Mg self-con catenation let L2def=L:L, similarlyL3;L4;:::. AlsoL0def=f"g. S. C. Kleene p roposednotation Lto denoteclosure of self-concatenation operation, i.e.Ldef=[i0Li. Examples L=f"gandL=f0;1gAshutosh TrivediLecture 3: Regular Expressions Ashutosh Trivedi { 4 of 21Regular Expressions (RegEx) textual ( declarative ) way to represent regular languages (compare automata) Users of UNIX-based systems will already b efamilia rwith these expressions: {ls lecture*.pdf {rm -rf *.* {grep automat* /usr/share/dict/words

Also used in A WK,exp r,Emacs and vi sea rches,

Lexi calanalysis t oolsli ke

exuse it for deningtok ens{Some useful String-set op erations: uni onL[Mdef=fw:w2Lorw2Mg concatenation L:Mdef=fu:v:u2Landv2Mg self-con catenation let L2def=L:L, similarlyL3;L4;:::. AlsoL0def=f"g. S. C. Kleene p roposednotation Lto denoteclosure of self-concatenation operation, i.e.Ldef=[i0Li. Examples L=f"gandL=f0;1gAshutosh TrivediLecture 3: Regular Expressions Ashutosh Trivedi { 5 of 21Regular Expressions: Inductive Denition For a regular expressionEwe writeL(E) for its language. The set of valid regular expressionsRegExcan be dened recursively as the following:

Syntax Semantics

empty string )"2RegEx L(") =f"g (empty set); 2RegEx L(;) =; (single letter)a2RegEx L(a) =fag (variable)L2RegExwhereLis a language variable. (union)E+F2RegEx L(E+F) =L(E)[L(F) (concatenation)E:F2RegEx L(E:F) =L(E):L(F) (Kleene Closure)E2RegEx L(E) = (L(E)) (Parenthetic Expression) (E)2RegEx L((E)) =L(E):

Precedence Rules:> : >+

Example : 01

+ 10def= (0:(1)) + ((1):(0))Ashutosh TrivediLecture 3: Regular Expressions Ashutosh Trivedi { 6 of 21Regular Expressions: Examples Find regular expressions for the following languages:

The set of all strings with an even numb erof 0's

The set of all strings of even length (length multiple of k)

The set of all strings that b eginwith 110

The set of all strings containing exactly three 1's

The set of all strings divisible b y2

The set of strings where third last symb olis 1 {Practice writing regula rexp ressionsfo rthe languages accepted b ynite

state automata.{Can w egeneralize this intuitive construction? Can w econstruct a DF A/NFAfo ra regula rexp ression?

Ashutosh TrivediLecture 3: Regular Expressions

Ashutosh Trivedi { 6 of 21Regular Expressions: Examples Find regular expressions for the following languages:

The set of all strings with an even numb erof 0's

The set of all strings of even length (length multiple of k)

The set of all strings that b eginwith 110

The set of all strings containing exactly three 1's

The set of all strings divisible b y2

The set of strings where third last symb olis 1 {Practice writing regula rexp ressionsfo rthe languages accepted b ynite

state automata.{Can w egeneralize this intuitive construction? Can w econstruct a DF A/NFAfo ra regula rexp ression?

Ashutosh TrivediLecture 3: Regular Expressions

Ashutosh Trivedi { 6 of 21Regular Expressions: Examples Find regular expressions for the following languages:

The set of all strings with an even numb erof 0's

The set of all strings of even length (length multiple of k)

The set of all strings that b eginwith 110

The set of all strings containing exactly three 1's

The set of all strings divisible b y2

The set of strings where third last symb olis 1 {Practice writing regula rexp ressionsfo rthe languages accepted b ynite

state automata.{Can w egeneralize this intuitive construction? Can w econstruct a DF A/NFAfo ra regula rexp ression?

Ashutosh TrivediLecture 3: Regular Expressions

Ashutosh Trivedi { 7 of 21Finite Automata to Regular Expressions

Theorem

For every deterministic nite automatonAthere exists a regular expressionEA such thatL(A) =L(EA).Proof.

Let states of automaton Abef1;2;:::;ng.

Consider R(k)

i;jbe the regular expression whose language is the set of labels of path fromitojwithout visiting any state with label larger thank. Basis ):R(0) i;jcollects labels of direct paths fromitoj, {R(0) i;j=a1+a2++anif(i;ak) =jfor 1kn if i=jthen it also includes".

Induction

): ComputeR(k) i;jusingR(k1) i;j's.Ashutosh TrivediLecture 3: Regular Expressions

Ashutosh Trivedi { 8 of 21ComputingR(k)

i;jusingR(k1) i;jAshutosh TrivediLecture 3: Regular Expressions Ashutosh Trivedi { 9 of 21Finite Automata to Regular Expressions

Theorem

For every deterministic nite automatonAthere exists a regular expressionEA such thatL(A) =L(EA).Proof.

Let states of automaton Abef1;2;:::;ng.

Consider R(k)

i;jbe the regular expression whose language is the set of labels of path fromitojwithout visiting any state with label larger thank. Basis ):R(0) i;jcollects labels of direct paths fromitoj, {R(0) i;j=a1+a2++anif(i;ak) =jfor 1kn if i=jthen it also includes".

Induction

): ComputeR(k) i;jusingR(k1) i;j's. R (k) i;j=R(k1) i;j+R(k1) i;k:(R(k1) k;k):R(k1) k;j: {EAisR(n) i

0;f1+R(n)

i

0;f2++R(n)

i

0;fk.Ashutosh TrivediLecture 3: Regular Expressions

Ashutosh Trivedi { 10 of 21Alternative Method{Eliminating States

Shortcomings of previous reduction:

The p reviousmetho dw orksin all the settings, but i sexp ensive(up to n3 expressions, with a facto rof 4 blo wup in each step).

F oreach i;j;i0;j0, bothR(k+1)

i;jandR(k+1) i

0;j0store expression (R(k)

k;k). This duplication can b eavoided.

Alternative (more intuitive) method:

A \b east"in the middle:

Finite automata with regula rexp ressions

Remove all states except nal and initial st atesin an \intuitive" w ay. T rivialto write regula rexp ressionsfo rDF Awith only t wostates: an initia l and a nal one. The regula rexp ressionis union of this construction fo revery nal state.

Example

Ashutosh TrivediLecture 3: Regular Expressions

Ashutosh Trivedi { 11 of 21gure2

Ashutosh TrivediLecture 3: Regular Expressions

Ashutosh Trivedi { 12 of 21gure3

Ashutosh TrivediLecture 3: Regular Expressions

Ashutosh Trivedi { 13 of 21Regular Expressions to Finite Automata

Theorem

For every regular expressionEthere exists a deterministic nite automatonAE such thatL(E) =L(AE).Proof. Via induction on the structure of the regula rexp ressionsw esho wa reduction to nondeterministic nite automata with"-transitions. Result follo wsfo rmthe equivalence of such automata with DF A.

Ashutosh TrivediLecture 3: Regular Expressions

Ashutosh Trivedi { 14 of 21Regular Expressions to Finite Automata

Ashutosh TrivediLecture 3: Regular Expressions

quotesdbs_dbs14.pdfusesText_20