COMP3630/6360: Theory of Computation Semester 1, 2022
The Australian National University
Regular Expressions
Copyright By PowCoder代写 加微信 powcoder
This Lecture Covers Chapter 3 of HMU: Regular Expressions and Languages
Introduction to regular expressions and regular languages
Equivalence of classes of regular languages and languages accepted Algebraic laws of (abstract) regular expressions
Additional Reading: Chapter 3 of HMU.
Regular Expressions and Languages
Regular Expressions: Overview
ó So far: DFAs, NFAs were given a machine-like description
ó Regular expressions are user-friendly and declarative formulation
ó Regular expressions find extensive use.
ó Searching/finding strings/pattern matching or conformance in text-formatting
systems (e.g., UNIX grep, egrep, fgrep)
ó Lexical analyzers (in compilers) use regular expressions to identify tokens (e.g.,
Lex, Flex)
ó In Web forms to (structurally) validate entries (passwords, dates, email IDs)
ó A regular expression over an alphabet Σ is a string consisting of: ó symbols from Σ
ó constants: ∅,ε
ó operators: +, ∗ ó parantheses: (, )
ó Each regular expression r denotes a language L(r) ⊆ Σ∗
Regular Expressions and Languages
Regular Expressions: Definition
ó Regular expressions are defined inductively as follows: ó Basis:
B1 ∅ and ε are regular expressions, with L(∅) = ∅ and L(ε) = {ε}. B2 For each a ∈ Σ, a is a regular expression with L(a) = {a}.
ó Induction: If r and s are regular expressions, then:
I1 so is r∗ with L(r∗) = (L(r))∗
I2 soisr+s withL(r+s)=L(r)∪L(s) I3 soisrs withL(r·s)=L(r)·L(s)
I4 so is (r) with L((r)) = L(r).
ó Only those generated by the above induction are regular.
ó Remark: Some authors/texts use | instead of +. HMU uses +. ó Precedence Rules:
(·) > ∗ > · > +
where > is ‘binds more strongly than’, and both + and · associate to the left.
Regular Expressions and Languages
Regular Expressions: Examples
ó r = 0 + 11∗10 is a regular expression
ó with brackets that indicate precedence: r = 0 + (1(1∗)10)
ó with more brackets indicating associativity: r = 0 + ((1(1∗))1)0
ó Computing the language:
L(r) = L(0) ∪ L(11∗10)
= {0}∪L(1)·L(1∗)·L(1)·L(0)
= {0}∪{1}·{1}∗ ·{1}·{0}
= {0}∪{1}·{1n | n ≥ 0}∗ ·{1}·{0} = {1i 0 | i ̸= 1}
ó Q: What’s a regular expression that describes alternating sequences of 0s and 1s?
DFAs and Regular Languages
Regular Languages: Some Basic Properties
Theorem 3.2.1
Let w ∈ Σ∗. Then {w} is regular. Proof of Theorem 3.2.1
ó By induction on the length of w. For w = ε, {w} = L(ε). For w of the form w′x, we have r s.t. {w′} = L(r) so that {w} = {wx} = L(rx).
Theorem 3.2.2
Let L1 and L2 be regular languages. Then, L∗1 , L1 ∪ L2 and L1L2 are also regular. Proof of Theorem 3.2.2
By definition of L(r∗), L(r + s) and L(rs).
ó Corollary 1: The class of regular languages is closed under finite union and concatenation,i.e.,ifL1,…,Lk areregularlanguagesforanyk∈N,thenL1∪···Lk andL1···Lk arealsoregularlanguages.
ó Corollary 2: Any finite language is regular.
DFAs and Regular Languages
DFAs and Regular Languages
Theorem 3.2.3
For every regular language M, there exists a DFA A such that M = L(A). Proof of Theorem 3.2.3
ó WLOG, let Σ = {0, 1}. Let M be a regular language. Then, M = L(E ) for some regular expression E.
ó For each regular expression, we will devise an ε-NFA.
q0 0à1 q1
DFAs and Regular Languages
DFAs and Regular Languages
Proof of Theorem 3.2.3 (Cont’d)
ó Induction E∗: E
DFAs and Regular Languages
DFAs and Regular Languages
Proof of Theorem 3.2.3 (Cont’d)
ó Induction E + F:
E (E + F )
DFAs and Regular Languages
DFAs and Regular Languages
Proof of Theorem 3.2.1 (Cont’d)
ó Induction I3’: E
DFAs and Regular Languages
ó Is the inclusion strict?
ó Are there languages accepted by DFAs that are not regular?
Regular Languages
Languages accepted by DFAs, NFAs, Ý-NFAs
Finite languages
DFAs and Regular Languages
DFAs and Regular Languages
Theorem 3.2.4
For every DFA A, there is a regular expression E such that L(A) = L(E ).
Proof of Theorem 3.2.4
ó Let DFA A = (Q,Σ,δ,q0,F) be given.
ó Let us rename the states so that Q = {q0,q1,q2,…,qn−1).
ó For any string s1 …sk ∈ L(A), there is a path
q0 −→qi1 −→qi2 ···−→qik ∈F
ó Define: R(i,j,k) be the set of all input strings that move the internal state of A from qi to qj using paths whose intermediate nodes comprise only of ql, l < k.
ó Idea: prove that (a) each R(i, j, k) is regular, and (b) L(A) is a union of R(i, j, k)’s. 12/19
States qk ,. . . ,qn 1
States q0,...,qk 1
DFAs and Regular Languages
DFAs and Regular Languages
Proof of Theorem 3.2.4 (Cont’d)
ó Note that L(A) = R (0, j , n). (i.e., paths that start in q0 and end in an accepting j:qj∈F
statewithintermediatenodesq0,q1,...,qn−1 (allnodes))
ó L(A) will be regular if each R(i,j,k) to be regular. We now proceed by induction to
show that each R(i, j, k) is regular.
ó Basis: Consider R(i,j,0) for i,j ∈ {0,1,...,n − 1}.
ó R(i,j,0) consists of strings whose corresponding paths start in qi and end in qj
with intermediate nodes ql, l < 0.
⇒ No intermediate nodes
⇒ R (i , j , 0) contains strings that change state qi to qj directly ⇒ R(i,j,0)⊆{ε}∪Σ
⇒ R(i,j,0) is a regular language [Corollary 2]
ó Induction: LetR(i,j,l)beregularfori,j∈{0,...,n−1}and0≤l