编程代写 COMP3630/6360: Theory of Computation Semester 1, 2022

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