COMP3630/6360: Theory of Computation Semester 1, 2022
The Australian National University
Properties of Regular Expressions
Copyright By PowCoder代写 加微信 powcoder
This Lecture Covers Chapter 4 of HMU: Properties of Regular Languages
Pumping Lemma for regular languages
Some more properties of regular languages Decision properties of regular languages
Equivalence and minimization of automata
Additional Reading: Chapter 4 of HMU.
Pumping Lemma for Regular Languages
Pumping Lemma
ó We know: If a language is given by a regular expression, or a DFA, it is regular. ó What can we say if a language is defined by enumeration or by a predicate?
ó Is L = {w ∈ {0,1}∗ : w does not contain 10} regular?
ó IsL={0n1n :n≥0}regular?
ó How do we answer such questions without delving into each
ó Is there an inherent structure to the strings belonging to a regular language? Lemma 4.1.1 (Pumping Lemma for Regular Languages)
Let L be a regular language. There there exists an n ∈ N, n ≥ 1 (depending on L) such that for any string w ∈ L with |w| ≥ n, there exist strings x,y,z such that:
(1) w = xyz
(2) |xy| ≤ n
(3) |y| > 0
(4) xy i z ∈ L for i ∈ N ∪ {0}
Pumping Lemma for Regular Languages
Proof of the Pumping Lemma
ó Let DFA A = (Q,Σ,δ,q0,F) accept L, and let n := |Q|.
ó The claim is vacuously true if L contains only strings of length n − 1 or less.
ó SupposeLcontainsastringw=s1···sk ∈Lwith|w|=k≥n.
ó Then, there must be a sequence of transitions that move A from q0 to some final state upon reading w.
q0 =qi0 −→qi1 −→qi2 −→···−→qin −→···−→qik ∈F
n symbols and n + 1 states
ó SOME state must be visited (at least) twice. Let qia = qib for i0 ≤ ia < ib ≤ in.
y is read z is read
s1 sia sia+1 sib sib+1 sin sin+1 sik
q0 =qi0 −→···−→qia −→ ···−→qib −→ ···−→qin −→ ···−→qik ∈F
ó (4) holds since the path for xyiz is derived from the above either by deleting the subpath between qia and qib or by repeating it. All such paths end in qik ∈ F .
Pumping Lemma for Regular Languages
Applications of the Pumping Lemma
Using the Pumping Lemma, we can show ó L={0n1n :n≥0}isnotregular.
ó Suppose it is. By the pumping lemma, there exists k ≥ 1 such that any w ∈ L, |w| ≥ k can be split as w = xyz,|y| ≥ 1 and |xy| ≤ k s.t. xyiz ∈ L for all i ≥ 0.
ó this applies to the string w = 0k1k ∈ L. kk
0...00...00...01...1
ó As|xy|≤k,thismeansthatx=0i andy=0j,z=0p1k withi+j+p=k.
óBythepumpinglemma,xy0z∈Lbutxy0z=0i0pyk andi+p=k−j̸=kas j ≥ 1, contradiction.
ó L={w∈{0,1}∗ :|w|isaprime}isnotregular.
ó L = {wwR : w ∈ {0,1}∗} is not regular. [wR = w read from right to left].
Some More Properties
Additional Properties of Regular Languages
ó We already know regular languages are closed under:
ó union, intersection, concatenation, Kleene-∗ closure, and difference.
ó We’ll see three more operations under which regular languages are closed.
ó Let LR be the language obtained by reversing each string ((01)R = 10) Theorem 4.2.1
Let L be regular. Then LR := {wR : w ∈ L} is also regular.
Proof of Theorem 4.2.1
ó Let langauge L be accepted by DFA A.
ó Let A′ be the DFA obtained by: (a) Reversing each arrow in A; (b) swapping final and initial states; and (c) introduce ε-transitions to make initial state (of A′) unique.
ó Then LR is accepted by A′.
Some More Properties
Closure under Homomorphisms
ó Ahomomorphismisamaph:Σ1 →Σ∗2.
ó The map can be extended to strings by defining s1 ···sk → h(s1)···h(sk).
Theorem 4.2.2
Let L be regular. Then h(L) := {h(w) : w ∈ L} is also regular. Proof of Theorem 4.2.2
ó Let E be the regular expression corresponding to L
ó Let h(E) be the expression obtained by replacing symbols s ∈ Σ1 by h(s). ó Then h(E) is a regular expression over Σ2
ó By a straightforward induction argument, we can show that L(h(E)) = h(L(E)) Expressions Languages
E L(E) (language over ⌃1) hh
h(E) h(L(E)) = L(h(E)) (language over ⌃2)
Some More Properties
Closure under Inverse Homomorphisms
Theorem 4.2.3
Let L be regular. Then h−1(L) := {w : h(w) ∈ L} is also regular.
Proof of Theorem 4.2.3
ó Let DFA A = (Q,Σ2,δ,q0,F) accept L
ó Let DFA B = (Q,Σ1,γ,q0,F) where
γ(q,s) = δˆ(q,h(s))
[Depending on the input B mimics none, one, or many transitions of A]
ó Bydefinition,ε∈L(A)iffq0 ∈F iffε∈L(B)
ó By induction, we can show that
s1 ···sk ∈ L(B) ⇔ h(s1)···h(sk) ∈ L(A) = L
ó Hence, B accepts h−1(L).
Decision Properties of Regular Languages
Decision Properties
ó DFAs and regular expressions are finite representations of regular languages ó How do we ascertain if a particular property is satisfied by a language?
ó Is the language accepted by a DFA is non-empty?
ó Does the language accepted by a DFA contain a given string w? ó Is the language accepted by a DFA infinite?
ó Do two given DFAs accept the same language?
ó Given two DFAs A and B, is L(A) ⊆ L(B)?
ó We will look at the above 5 questions assuming that regular languages are defined by DFAs. (If the language is specified by an expression, we can convert it to a DFA!)
Decision Properties of Regular Languages
Decision Properties
ó Emptiness: If one is given a DFA with n states that accepts L, we can find all the states reachable from the initial state in O(n2) time. If no final state is reachable, L must be empty.
ó Membership: If one is given a DFA with n states that accepts L, given string w, we can simply identify the transitions corresponding to w one symbol at a time. If the last state is an accepting state, then w must be in the language. This takes no more than O(|w|) time steps.
ó Infiniteness: We can reduce the problem of infiniteness to finding a cycle in the directed graph (a.k.a. transition diagram) of the DFA.
ó First, delete any node unreachable from the initial node (O(n2) complexity).
ó Next, delete nodes that cannot reach any final node (O(n3) complexity).
ó Use depth-first search (DFS) to find a cycle in the remaining graph (O(n2) complexity).
Decision Properties of Regular Languages
Decision Properties (Cont’d)
ó Equivalence: Given A = (QA,Σ,δA,qA0,FA) and A = (QB,Σ,δB,qB0,FB), how do we ascertain if L(A) = L(B)?
L(A) = L(B) ⇔ L(A)∩L(B)c = ∅ L(A)c ∩L(B)=∅
Run A and B in parallel.
ó L(A) ∩ L(B)c : Accept if resp. paths ends in FA and FBc . ó L(A)c ∩ L(B ): Accept if resp. paths ends in FAc and FB .
ó Use product DFA: Construct C = (QC,Σ,δC,qC0,FC) defined by
QC = QA × QB [Cartesian Product] qC0 =(qA0,qB0)
δC ((q, q′), s) = (δA(q, s), δB (q′, s)) [Both DFAs are simulated in parallel]
FC = (FA × FBc ) ∪ (FAc × Fc ) [accept strings in exactly one of L(A) or L(B)]
L(A) = L(B) ⇔ L(C) = ∅
Decision Properties of Regular Languages
Decision Properties (Cont’d)
ó Inclusion: Given A = (QA,Σ,δA,qA0,FA) and A = (QB,Σ,δB,qB0,FB), how do we ascertain if L(A) ⊆ L(B)?
L(A) ⊆ L(B) ⇔ L(A)∩L(B)c = ∅ Run A and B in parallel.
ó L(A) ∩ L(B)c : Accept if resp. paths ends in FA and FBc .
ó Use product DFA: Construct C = (QC,Σ,δC,qC0,FC) defined by
QC = QA × QB
qC0 =(qA0,qB0)
δC ((q, q′), s) = (δA(q, s), δB (q′, s))
FC = (FA × FBc )
[Cartesian Product]
[Both DFAs are simulated in parallel]
[accept strings in exactly one of L(A) or L(B)]
L(A) ⊆ L(B) ⇔ L(C) = ∅
Minimizing the Number of States
DFA State Minmimization
ó Given two DFAs, we know how to test if they accept the same language.
ó Is there a unique minimal DFA for a given regular language?
ó Given a DFA, can we reduce the number of states without altering the language it accepts?
Clearly, the two DFAs accept the same language and state C is unnecessary.
ó How do we remove ‘unnecessary’ states without altering the underlying language?
Minimizing the Number of States
DFA State Minimimization
ó State minimization requires a notion of equivalence or distinguishability of states. ó Clearly, distinguishability of two states must be based on finality
states p and q are equivalent ⇔ or indistinguishable
states p and q are distinguishable ⇔
δˆ(p, w) ∈ F whenever δˆ(q, w) ∈ F for every w ∈ Σ∗.
exactly one of δˆ(p,w) or δˆ(q,w) is in F for some w ∈ Σ.
ó Table Filling Algorithm identifies equivalent and distinguishable pairs of states.
ó Any final state is distinguishable from a non-final state (and vice versa)
ó If (a) p and q are distinguishable; (b) δˆ(p′, s) = p and (c) δˆ(q′, s) = q, then p′
and q′ are also distinguishable
Minimizing the Number of States
Identifying pairs of (In)distinguishable States: An Example
ó Fill in × whenever one component of pair is final, and other is not. ó Fill in × if 1 moves the pair of states to a distinguishable pair
ó Fill in × if 0 moves the pair of states to a distinguishable pair
ó Repeat until no progress
Theorem 4.4.1
Any two states without a × sign are equivalent.
ó Proof idea: If two states are distinguishable, the algorithm will fill a × eventually.
Minimizing the Number of States
Table-filling Algorithm
ó Delete states not reachable from start states
ó Delete any non-starting state that cannot reach any
final state
ó Find distinguishable and equivalent pair of states
ó Find equivalence classes of indistinguishable states. In this example: {A},{B},{C,E},{D,F},{G}
ó Simply collapse each equivalence class of states to a state
ó Delete parallel transitions with same label.
Remark: The resultant transition diagram will be a DFA.
Minimizing the Number of States
Table-filling: Other Uses
ó Test equivalence of languages accepted by 2 DFAs.
ó Given A = (QA,Σ,δA,qA0,FA) and B = (QB,Σ,δB,qB0,FB):
ó Rename states in QB so that QA and QB are disjoint. ó View A and B together as one DFA
(Ignore the fact that there are 2 start states)
ó Run table-filling on QA ∪ QB .
ó qA0 and qB0 are indistinguishable ⇔ L(A) = L(B).
[Why?] If w distinguishes qA0 from qB0 then w cannot be in both L(A) and L(B)
ó Suppose a DFA A cannot be minimized further by table-filling. Then, A has the least number of states among all DFAs that accept L(A)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com