Formal Language Theory Problem Sheet 1
Find regular expression for the set {anbm : (n + m) is even}. 5. Give a regular expression for the following languages: (a) L = {anbm : n ? 4m ? 3}.
Lecture 4: Regular Expressions and Finite Automata
La?b? = {w ? ?? : w is of the form anbm for n m ? 0} Kleene's regular expressions
Homework 3 Solutions
Answer: Let NFA N = (Q ?
Solution to Problem Set 1
21-Jan-2003 L = {w
Graduate Program Department of Computer Science
determine the cause of the problem. A) module. B) debugger A regular expression for the set {anbm: n ? 3 m is odd} can be: (A). aaab. (B). aaabbb.
Homework 5 Solutions
(a) Your task is to design a CFG G with set of terminals T that generates exactly the regular expressions with alphabet {0 1}.
q1 q2 q3 a b b a a b
Regular Expressions. • Nonregular Languages. CS 341: Chapter 1. 1-3. Introduction Definition: If A is the set of all strings that machine M accepts.
Practice Problems for Final Exam: Solutions CS 341: Foundations of
Answer: A language is regular if and only if it has a regular expression. There exist constants c and n0 such that
Written Assignment I Solutions
Write a regular expression for this language. • The NFA recognizes all strings that contain two 0's separated by a substring whose length is a multiple of 3. •
an-introduction-to-formal-languages-and-automata-5th-edition-2011
Find a regular expression for the set {anbm:( n + m) is even}. 6. Give regular expressions for the following languages. (a) L. 1. = {nbm: n ? 4m ? 3}.
Find a regular expression for the set {anbm: n ? 3 m is odd} - Chegg
Answer to Solved Find a regular expression for the set {anbm: n ? 3 m You'll get a detailed solution from a subject matter expert that helps you
[PDF] Automata Theory Assignment Due: May 9 2008 (before Class)
Automata Theory Assignment #3 Due: May 9 2008 (before Class) 1 (10 pts) Find a regular expression for the set {anbm : n ? 3m is even} Answer:
[PDF] CS21004 - Tutorial 4 - CSE IIT Kgp
Find the regular expressions for the following languages on {a b} a L = {anbm : n ? 4m ? 3} Solution: Generate 4 or more a s follows by the requisite
[PDF] Formal Language Selected Homework Chapter 31
Find a regular expression for the set {a"b":n? 3 m is even} string is not in L if it is of the form anbm with either n < 4 or m> 3 but this does
[Solved] Consider the language L = {anbm ? n ? 4 m ? 3} Whi
From the language L = {anbm ? n ? 4 m ? 3} we can observe that In the regular expression there should be at least 4 a(s) In the r
[PDF] Homework 3 Solutions
Answer: Let NFA N = (Q ? ? 1F) where Q = {1 2 3} ? = {a b} 1 is (b) Prove that L has a regular expression where L is the set of strings
[PDF] Regular Expression & Regular Languages
A regular expression consists of strings of symbols from some alphabet ? Construct a RE for the set {anbm: n >=3 m is even}
[PDF] CSCI 3434: Theory of Computation - Lecture 4: Regular Expressions
La?b? = {w ? ?? : w is of the form anbm for n m ? 0} Kleene's regular expressions also appeared as Type-3 languages in ls lecture* pdf
:
Ashutosh Trivedi { 1 of 1CS 208: Automata Theory and Logic Lecture 4: Regular Expressions and Finite Automata Ashutosh TrivediAstartBb
8x(La(x)! 9y:(x ba Department of Computer Science and Engineering,
Indian Institute of Technology Bombay.Ashutosh TrivediLecture 4: Regular Expressions and Finite Automata
Ashutosh Trivedi { 2 of 1What 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 4: Regular Expressions and Finite Automata Ashutosh Trivedi { 2 of 1What 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 4: Regular Expressions and Finite Automata Ashutosh Trivedi { 3 of 1Why 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 4: Regular Expressions and Finite Automata Ashutosh Trivedi { 3 of 1Why 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 4: Regular Expressions and Finite Automata Ashutosh Trivedi { 3 of 1Why 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 4: Regular Expressions and Finite Automata Ashutosh Trivedi { 4 of 1Regular 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 cite p roposednotation Lto denoteclosure of self-concatenation operation, i.e.Ldef=[i0Li. Examples L=f"gandL=f0;1gAshutosh TrivediLecture 4: Regular Expressions and Finite Automata Ashutosh Trivedi { 4 of 1Regular 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 cite p roposednotation Lto denoteclosure of self-concatenation operation, i.e.Ldef=[i0Li. Examples L=f"gandL=f0;1gAshutosh TrivediLecture 4: Regular Expressions and Finite Automata Ashutosh Trivedi { 5 of 1Regular 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 4: Regular Expressions and Finite Automata Ashutosh Trivedi { 6 of 1Regular 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 4: Regular Expressions and Finite Automata Ashutosh Trivedi { 6 of 1Regular 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 4: Regular Expressions and Finite Automata Ashutosh Trivedi { 6 of 1Regular 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 4: Regular Expressions and Finite Automata Ashutosh Trivedi { 7 of 1Finite Automata to Regular Expressions Theorem
For every deterministic nite automaton A there exists a regular expression E A such that L(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 4: Regular Expressions and Finite Automata Ashutosh Trivedi { 8 of 1ComputingR(k)
i;jusingR(k1) i;jAshutosh TrivediLecture 4: Regular Expressions and Finite Automata Ashutosh Trivedi { 9 of 1Finite Automata to Regular Expressions Theorem
For every deterministic nite automaton A there exists a regular expression E A such that L(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 4: Regular Expressions and Finite Automata
Ashutosh Trivedi { 10 of 1Alternative 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 4: Regular Expressions and Finite Automata Ashutosh Trivedi { 11 of 1gure2
Ashutosh TrivediLecture 4: Regular Expressions and Finite Automata Ashutosh Trivedi { 12 of 1gure3
Ashutosh TrivediLecture 4: Regular Expressions and Finite Automata Ashutosh Trivedi { 13 of 1Regular Expressions to Finite Automata Theorem
For every regular expression E there exists a deterministic nite automaton A E such that L(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 4: Regular Expressions and Finite Automata Ashutosh Trivedi { 14 of 1Regular Expressions to Finite Automata Ashutosh TrivediLecture 4: Regular Expressions and Finite Automata Ashutosh Trivedi { 15 of 1Regular Expressions to Finite Automata Ashutosh TrivediLecture 4: Regular Expressions and Finite Automata Ashutosh Trivedi { 16 of 1Syntactic Sugar for Regular Expressions in Unix [a1a2a3:::ak] fora1+a2++ak :fora+b++z+A+::: jfor + Rf5gforRRRRR
R+ for[i1Rfig
R? for"+R
Also [A-za-z0-9] ,[:digits:], etc.
Applications
Check the man page of \
grep " (regular expression based search tool) and lex " (A tool to generate regular expressions based pattern matching tool) to learn more about regular expressions on UNIX based systems. Ashutosh TrivediLecture 4: Regular Expressions and Finite Automata Ashutosh Trivedi { 17 of 1Algebraic Laws for Regular Expressions Associativity
{L+ (M+N) = (L+M) +NandL:(M:N) = (L:M):N. Commutativity
{L+M=M+L. However,L:M6=M:Lin general. Identity
{;+L=L+;=Land":L=L:"=L Annihilator
{;:L=L:;=; Distributivity
left distributivit yL:(M+N) =L:M+L:N. right distributivit y( M+N):L=M:L+N:L. IdempotentL+L=L.
Closure Laws
( L)=L,;=","=",L+=LL=LL, andL=L++".quotesdbs_dbs21.pdfusesText_27
Department of Computer Science and Engineering,
Indian Institute of Technology Bombay.Ashutosh TrivediLecture 4: Regular Expressions and Finite Automata
Ashutosh Trivedi { 2 of 1What 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 ofa0sgDeterministic 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 4: Regular Expressions and Finite Automata Ashutosh Trivedi { 2 of 1What 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 ofa0sgDeterministic 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 4: Regular Expressions and Finite AutomataAshutosh Trivedi { 3 of 1Why 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 asT ype-3langu ages
inChomsky's hierarchy [Cho59].
Monadic second-o rderlogic
denable languages [B60, 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 4: Regular Expressions and Finite AutomataAshutosh Trivedi { 3 of 1Why 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 asT ype-3langu ages
inChomsky's hierarchy [Cho59].
Monadic second-o rderlogic
denable languages [B60, 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 4: Regular Expressions and Finite AutomataAshutosh Trivedi { 3 of 1Why 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 asT ype-3langu ages
inChomsky's hierarchy [Cho59].
Monadic second-o rderlogic
denable languages [B60, 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 4: Regular Expressions and Finite Automata Ashutosh Trivedi { 4 of 1Regular 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/wordsAlso 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 cite p roposednotation Lto denoteclosure of self-concatenation operation, i.e.Ldef=[i0Li. Examples L=f"gandL=f0;1gAshutosh TrivediLecture 4: Regular Expressions and Finite Automata Ashutosh Trivedi { 4 of 1Regular 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/wordsAlso 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 cite p roposednotation Lto denoteclosure of self-concatenation operation, i.e.Ldef=[i0Li. Examples L=f"gandL=f0;1gAshutosh TrivediLecture 4: Regular Expressions and Finite Automata Ashutosh Trivedi { 5 of 1Regular 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 4: Regular Expressions and Finite Automata Ashutosh Trivedi { 6 of 1Regular 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'sThe 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 4: Regular Expressions and Finite Automata Ashutosh Trivedi { 6 of 1Regular 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'sThe 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 4: Regular Expressions and Finite Automata Ashutosh Trivedi { 6 of 1Regular 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'sThe 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 4: Regular Expressions and Finite Automata Ashutosh Trivedi { 7 of 1Finite Automata to Regular ExpressionsTheorem
For every deterministic nite automaton A there exists a regular expression E A such that L(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 4: Regular Expressions and Finite AutomataAshutosh Trivedi { 8 of 1ComputingR(k)
i;jusingR(k1) i;jAshutosh TrivediLecture 4: Regular Expressions and Finite Automata Ashutosh Trivedi { 9 of 1Finite Automata to Regular ExpressionsTheorem
For every deterministic nite automaton A there exists a regular expression E A such that L(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) i0;f1+R(n)
i0;f2++R(n)
i0;fk.Ashutosh TrivediLecture 4: Regular Expressions and Finite Automata
Ashutosh Trivedi { 10 of 1Alternative Method{Eliminating StatesShortcomings 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) i0;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 4: Regular Expressions and Finite AutomataAshutosh Trivedi { 11 of 1gure2
Ashutosh TrivediLecture 4: Regular Expressions and Finite AutomataAshutosh Trivedi { 12 of 1gure3
Ashutosh TrivediLecture 4: Regular Expressions and Finite Automata Ashutosh Trivedi { 13 of 1Regular Expressions to Finite AutomataTheorem
For every regular expression E there exists a deterministic nite automaton A E such that L(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 4: Regular Expressions and Finite Automata Ashutosh Trivedi { 14 of 1Regular Expressions to Finite Automata Ashutosh TrivediLecture 4: Regular Expressions and Finite Automata Ashutosh Trivedi { 15 of 1Regular Expressions to Finite Automata Ashutosh TrivediLecture 4: Regular Expressions and Finite Automata Ashutosh Trivedi { 16 of 1Syntactic Sugar for Regular Expressions in Unix [a1a2a3:::ak] fora1+a2++ak :fora+b++z+A+::: jfor +Rf5gforRRRRR
R+ for[i1Rfig
R? for"+R
Also [A-za-z0-9] ,[:digits:], etc.
Applications
Check the man page of \
grep " (regular expression based search tool) and lex " (A tool to generate regular expressions based pattern matching tool) to learn more about regular expressions on UNIX based systems. Ashutosh TrivediLecture 4: Regular Expressions and Finite Automata Ashutosh Trivedi { 17 of 1Algebraic Laws for Regular ExpressionsAssociativity
{L+ (M+N) = (L+M) +NandL:(M:N) = (L:M):N.Commutativity
{L+M=M+L. However,L:M6=M:Lin general.Identity
{;+L=L+;=Land":L=L:"=LAnnihilator
{;:L=L:;=;Distributivity
left distributivit yL:(M+N) =L:M+L:N. right distributivit y( M+N):L=M:L+N:L.IdempotentL+L=L.
Closure Laws
( L)=L,;=","=",L+=LL=LL, andL=L++".quotesdbs_dbs21.pdfusesText_27
[PDF] find a regular expression for the set a^nb^m (n+m) is odd
[PDF] find a regular expression for the set {anbm:( n + m) is even}.
[PDF] find a regular grammar that generates the language l (aa* (ab+ a)*).
[PDF] find all complex solutions calculator
[PDF] find an inmate
[PDF] find coinbase account number
[PDF] find connected components in directed graph
[PDF] find death notices
[PDF] find degree of vertex in graph
[PDF] find my 1099 misc online
[PDF] find my twitter account
[PDF] find object type javascript
[PDF] find octagonal prism volume
[PDF] find perfect square trinomial calculator
[PDF] find the basic feasible solution
[PDF] find a regular expression for the set {anbm:( n + m) is even}.
[PDF] find a regular grammar that generates the language l (aa* (ab+ a)*).
[PDF] find all complex solutions calculator
[PDF] find an inmate
[PDF] find coinbase account number
[PDF] find connected components in directed graph
[PDF] find death notices
[PDF] find degree of vertex in graph
[PDF] find my 1099 misc online
[PDF] find my twitter account
[PDF] find object type javascript
[PDF] find octagonal prism volume
[PDF] find perfect square trinomial calculator
[PDF] find the basic feasible solution
