The Australian National University Semester 1, 2022 Research School of Computer Science Tutorial 2
Theory of Computation
This tutorial sheet contains way more exercises that you will be able to solve or discuss in the tutorial.
Exercise 1 DFA
Copyright By PowCoder代写 加微信 powcoder
Here is the transition diagram of a simple, deterministic automaton with start state q0 and accepting state q1.
Show that this automaton accepts exactly those strings with an odd number of 1’s using induction. Solution. We write A for the above automaton, and show that
q0 w has an even numbner of 1’s δˆ(q0, w) = q1 w has an odd number of 1’s
This implies the claim, as w ∈ L(A) ⇐⇒ δˆ(q0, w) = q1 ⇐⇒ w has an odd number of 1’s.
The base case w = ε is evident, as δˆ(q0, ε) = q0 and ε has an even number of 1’s. Now assume that w is
of the form w = w′s with s ∈ Σ.
Let δˆ(q0,w′) = qi, so that by induction hypothesis, i = 0 if w′ has an even number of 1’s, and i = 1,
otherwise. We write |x|1 for the number of 1’s in a string x.
If s = 1, then δˆ(q0, w′s) = δ(δˆ(q0, w), s) = δ(qi, s) = q1−i. Then
|w|1 = |w′s|1 even ⇐⇒ |w|1 odd ⇐⇒ δˆ(q0, w′) = q1 ⇐⇒ δˆ(q0, w′s) = q0 |w|1 = |w′s|1 odd ⇐⇒ |w|1 even ⇐⇒ δˆ(q0, w′) = q0 ⇐⇒ δˆ(q0, w′s) = q1
as required. If, on the other hand, s = 0, we have that δˆ(q0, w′s) = δ(δˆ(q0, w′), 0) = δ(qi, 0) = qi. Then |w|1 = |w′s|1 even ⇐⇒ |w|1 even ⇐⇒ δˆ(q0, w′) = q0 ⇐⇒ δˆ(q0, w′s) = q0
|w|1 = |w′s|1 odd ⇐⇒ |w|1 odd ⇐⇒ δˆ(q0, w′) = q1 ⇐⇒ δˆ(q0, w′s) = q1 which finishes the proof.
Exercise 2 ε-NFA
Consider the following ε-NFA, presented as both a diagram and a table for reference.
εabc →p ∅ {p} {q} {r}
q {p} {q} {r} ∅ ∗r {q} {r} ∅ {p}
(a) Compute the ε-closure of each state. Solution.
ECLOSURE(p) = {p} ECLOSURE(q) = {p, q} ECLOSURE(r) = {p, q, r}
(b) Give all the strings of length two or less accepted by the automaton. Solution. We enumerate the possible options, and obtain the list
{c, ac, bb, bc, ca, cb, cc}
Note that bc, cb, cc are easily missed, and require use of the epsilon transitions to finish reading the
string in a final state.
(c) Convert the automaton to a DFA.
We perform subset construction, keeping in mind to include the states that are reachable by including ε transitions before or after each character.
→ {p} {p} {p,q} {p,q,r} {p,q} {p,q} {p,q,r} {p,q,r} *{p,q,r} {p,q,r} {p,q,r} {p,q,r}
By denoting Sp = {p}, Spq = {p, q}, Spqr = {p, q, r}, we can draw the following transition diagram.
Exercise 3
Design ε-NFAs for the following languages. Also, design NFAs for the following languages. Compare the two designs (hopefully your ε-NFA’s are less complex.)
1. Any string that has zero or more a’s, followed by zero or more b’s, followed by zero or more c’s. Solution.
S0 ε S1 ε S2 c
S0 b S1 c S2 abc
2. Any string of the form ab repeated zero or more times, or ca repeated one or more times. Solution.
εc S3 c S4 a S5
a ab aba b
3. Any binary string with a 1 somewhere in the last 5 characters.
S0 1 S1 0,1,ε S2 0,1,ε S3 0,1,ε S4 0,1,ε S5 1
S0 1 S1 0,1 S2 0,1 S3 0,1 S4 0,1 S5 0,1 1
4. Any string of the form 0k where k is a multiple of two or three. Solution.
1′ 0 2′ 00
Exercise 4
If L1 and L2 are both regular languages, is it always the case that L1\L2 ={w∈L1 :w̸∈L2}
is regular? Provide a proof or a counterexample. (Phrasing set difference in terms of other operations might help.)
Solution. Yes, note that fact that L1\L2 = L1 ∩ Lc2, and then prove closure under intersection and complements.
Closure under Complement. If L is regular, then L = L(A) for some DFA A. Let Ac the same automaton as A, but where a state is final in Ac iff it is not final in A. Then L(Ac) = L(A)c showing closure under complements.
Closure under intersection. This follows from closure under complement and closure under union, as L 1 ∩ L 2 = ( L c1 ∪ L c2 ) c .
Together, we have closure under set-difference, as outlined above.
Exercise 5
Let A = (Q,Σ,δ,q0,F) be a DFA. Show that
δˆ(q, uv) = δˆ(δˆ(q, u), v))
for all states q ∈ Q and all strings u,v ∈ Σ∗.
Solution. We do induction on the (second) string v. If v = ε, then δˆ(δˆ(q, u), v) = δˆ(δˆ(q, u), ε) = δˆ(q, u) =
δˆ(q, uε) as required.
If v = v′x with x ∈ Σ and v′ ∈ Σ∗, we have δˆ(δˆ(q,u),v′x) = δ(δˆ(δˆ(q,u),v′),x) = δ(δˆ(q,uv′),x) = δˆ(q,uv′x) where we have used the definition of δˆ in for the first and last equality, and the inductive hypothesis or the second.
Exercise 6
Let Σ be a (finite) alphabet and L ⊆ Σ∗ a language. Two strings u, w ∈ Σ∗ are called L-equivalent iff ∀x∈Σ∗(ux∈L ⇐⇒ wx∈L).
We write RL for the relation of L-equivalence, that is RL = {(u, w) ∈ Σ∗ | u and v are L-equivalent}.
1. Show that RL is an equivalence relation. Solution.
Reflexivity. Letu∈Σ∗.Weshowthat(u,u)∈RL.Toseethis,letx∈Σ∗.Thenux∈L ⇐⇒ ux ∈ L whence (u,u) ∈ RL.
Symmetry. Assume that (u,w) ∈ RL. We show that (w,u) ∈ RL. So assume that x ∈ Σ∗. Then byassumption,ux∈L ⇐⇒ wx∈Landhencetrivalywx∈L ⇐⇒ ux∈L.
Transitivity. Assume that (u,w) ∈ RL and (w,v) ∈ RL. Let x ∈ Σ∗. We show ux ∈ L ⇐⇒ vx ∈ L. So assume ux ∈ L. Then wx ∈ L as (u,w) ∈ RL. This implies vx ∈ L as (w,v) ∈ RL. The same argument shows that vx ∈ L ⇐⇒ ux ∈ L.
2. Let A = (Q,Σ,δ,q0,F) be a deterministic inite automaton and let L = L(A). Write S(q) = {w ∈ Σ∗ | δˆ(q0, w) = q} for the set of strings that move the automaton from the inital state to the state q. (In particular, this implies that L(A) = {S(q) | q ∈ F}.) Show that, for any state q ∈ Q, any two elements in S(q) are L-equivalent. In symbols:
∀q ∈ Q.∀u,w ∈ S(q).(u,w) ∈ RL
Solution. Letq∈Qandletu,w∈S(q).Letx∈Σ∗.Weshowthatux∈L ⇐⇒ wx∈L. So assume that ux ∈ L. By definition, δˆ(q0,ux) ∈ F. But δˆ(ux,q0) = δˆ(δˆ(q0,u),x) = δˆ(q,x) = δˆ(δˆ(q0, w), x) = δˆ(q0, wx) so that δˆ(q0, wx) ∈ F whence wx ∈ L.
Here, we have used that u,w ∈ S(q) by definition mens that δˆ(q0,u) = δˆ(q0,w) = q and that in general, δˆ(q, xy) = δˆ(δˆ(q, x), y). The latter we have established in a previous exercise.
3. Hence, or otherwise, establish that if L is regular, the number of equivalence classes of RL is finite. In other words, if [u] = {w ∈ Σ∗ | (u,w) ∈ RL} is the equivalence class of u ∈ Σ∗, then the set {[u] | u ∈ Σ∗} is finite.
Solution. Consider the function
s : {q ∈ Q | S(q) ̸= ∅} → {[x] | x ∈ Σ∗}
defined by
q → the unique [x] with S(q) ⊆ [x].
We show that this function is both well-defined and surjective, and the claim follows from the set Q (and hence the subset that of Q that is the domain of s) being finite. We first show that s is well defined, i.e. for every q ∈ Q:
• there exists x ∈ Σ∗ such that S(q) ⊆ [x]
• ifS(q)⊆[x]andS(q)⊆[y],then[x]=[y].
For the first item, let x ∈ S(q). We claim that S(q) ⊆ [x] which follows from the fact that any two elements in S(q) are RL-equivalent. For the second item, suppose that S(q) ⊆ [x] and S(q) ⊆ [y] and let u ∈ S(q). Then in particular, u ∈ [x] so that (u,x) ∈ RL. For the same reason, (u,y) ∈ RL. As RL is an equivalence relation, we obtain (x, y) ∈ RL so that [x] = [y].
We now show that s is surjective. So let x ∈ Σ∗. We have to find q ∈ Q with S(q) ̸= ∅ so that S(q) ⊆ [x]. But this is easy: we put q = δˆ(q0, x). To see that S(q) ̸= ∅ first notice that x ∈ S(q) by definition. To see that S(q) ⊆ [x], let u ∈ S(q). Then (u, x) ∈ RL as we had estabished earlier. As RL is an equivalence relation, we have that u ∈ [x] as desired.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com