The Australian National University Semester 1, 2022 Research School of Computer Science Tutorial 3
Theory of Computation
This tutorial sheet contains way more exercises that you will be able to solve or discuss in the tutorial. Exercises with a ! denote harder ones, !! denotes very difficult, and !!! denotes challenge exercises beyond the scope of the course.
Exercise 1 Checking Regularity
Copyright By PowCoder代写 加微信 powcoder
For each of the following languages, either prove that it is regular, or that it is not regular.
1. The set of strings over alphabet {a, b, c} containing at least one a and at least one b.
Solution. Yes, we can provide regular expression for “containing at least one a” and “containing at least one b”
(a+b+c)∗a(a+b+c)∗ (a+b+c)∗b(a+b+c)∗ and then note regular languages are closed under intersection.
2. The set of strings of 0’s and 1’s with at most one pair of consecutive 1’s, that is, all strings w that cannot be written as w = w111w211w3 for w1, w2, w3 ∈ Σ∗.
Solution. Yes, can provide a DFA: 00
S0 S11S2 S31T
Or we can show that the complement of the language, that is, {w111w211w3 | w1, w2, w3} is regular, and use the fact that regular languages are closed under complement. The latter language is regular, as it is the language of the regular expression (0 + 1)∗11(0 + 1)∗11(0 + 1)∗.
3. {an |n=2k forsomek∈N}
Solution. No, we prove via pumping lemma. Assume that the language above (denoted L) is regular. Then there exists some n such that for all strings w ∈ L with |w| ≥ n, pumping lemma applies. Choose w = a2m , where m = max(3, n). Clearly, |w| = 2m ≥ 2n > n. Then, by pumping lemma,webreakupw=xyz,with|xy|≤mandy̸=ε.So,y=aj with0
6. ! The set of strings over the alphabet of all ASCII characters that are syntactically valid Haskell programs.
Solution. No, note that f=[]
f=[[[[]]]]
are all valid programs, and we could use pumping lemma to pump up the brackets on one side to get an invalid program, by choosing our string w to be the program f=[n]n. We decompose w = xyz, and then deleting y either removes the f, or the = (which would make the program syntactically invalid), or removes some left square brackets, unbalancing the number of brackets. In either case, the resulting string would not be a valid Haskell program.
7. !! {w ∈ {0, 1}∗ : w is divisible by 3 when interpreted as a binary number} (Hint: Consider how to formally state that a binary number is divisible by 3.) Solution. A binary number bnbn−1 . . . b1b0 has the value
n 2ibi i=0
We need to check if the above value is congruent to 0 modulo 3. Note that 2 ≡ −1 mod 3, so
2ibi mod 3 ≡ (2ibi mod 3) ≡ (2 mod 3)i(bi mod 3) ≡ (−1)ibi mod 3 i=0 i=0 i=0 i=0
So we need to check if the alternating sum of bits is congruent to 0 modulo 3. We will have 6 states, to remember the current sum so far (up to modulo 3) and whether to add or subtract the next bit, and then transition as appropriate to keep track of the current sum value. We accept if the sum value is 0 at the end. Note that we can assume that the first bit is always positive, as if it isn’t, we still get the same result, as −1 ≡ 2, −2 ≡ 1 and 0 ≡ 0.
1Euclid, c. 300BC
0,+ 1,− 010
Author’s Note: I haven’t checked whether this DFA is minimal, but we don’t need to do that to solve this exercise.
Exercise 2 Algorithms for Regular Languages In the following, we write L(R) for the language of a regular expression R.
1. Describe an algorithm that, for a regular expression R, determines whether or not L(R) = ∅.
Solution. Convert the regular expression to an ε-NFA with the construction from the lecture slides, convert that ε-NFA to a DFA via subset construction, and then use breadth first search to try and find a path to a final state (if any exist). If there is no reachable final state, then the language is empty.
2. ! Describe an algorithm that, for given regular expressions R1 and R2, determines whether L(R1) ⊆ L(R2). (Hint: think of how you could use the previous exercise.)
Solution. Note that L1 ⊆ L2 if and only if L1\L2 = ∅. Note that L1\L2 = (Lc1 ∪ L2)c (Draw a Venn diagram if you don’t believe me.) Now, take the regular expression for L1, and convert to a DFA D1 using the construction from the lecture slides. Do the same to L2 to obtain D2. Flip accepting and rejecting states in D1 to obtain D1c, which satisfies L(D1c) = Lc1. Construct the ε-NFA E by combining D1c and D2 under the union construction. Note that L(E) = Lc1 ∪ L2. Convert E to a DFA DE using subset construction, and then swap accepting and final states of the result to obtain DEc , which satisfies
L ( D Ec ) = ( L c1 ∪ L 2 ) c Then, check if L(DEc ) is empty using the previous exercise.
3. ! Describe an algorithm that, for a given regular expression R, computes a regular expression for the reversal of R, that is, a regular expression S such that
L(S)={w∈Σ∗ | thereversalofwisinL(R)}
Use your algorithm to find the reversal of (001 + 1∗)∗001∗ (as a regular expression).
Solution. We define the algorithm recursively:
∅R = ∅ εR = ε ∀σ∈Σ,σR =σ
(A+B)R =AR +BR (A∗)R = (AR)∗ (AB)R = BRAR
The justification of the last few rules being that if we are taking the reversal of a string from A + B, it’s the reversal of something from A, or from B. If it’s something from the reversal of A∗, then it’s something from the reversal of A, copied as many times as required, which is (AR)∗, and that to reverse the concatenation of two strings, we reverse both, and swap them, hence the rule ABR = BRAR.
With that in mind, the reversal of (001 + 1∗)∗001∗ is 1∗00(100 + 1∗)∗. Exercise 3 Brzozowski Derivatives
Let Σ be an alphabet. Given a language L ⊆ Σ∗ and x ∈ Σ, we define the Brzozowski derivative of L with respect to x ∈ Σ as
dL ={w∈Σ∗ :xw∈L} dx
that is, all strings that when prefixed with x, are in the language L. In the following, we call a language L non-trivial if L ̸= ∅ and L ̸= Σ∗ and fix the alphabet Σ = {0,1}.
1. Let L = {0, 00, 10, 111}. Compute dL and dL . d0 d1
dL = {ε, 0} d0
dL = {0, 11} d1
2. Find a non-trivial language L such that dL = L and dL = ∅. d0 d1
Solution. Choose L = L(0∗). Then any string of zeros is still a string of zeros with a zero prepended,so dL =L.Thereisnostringwsuchthat1w∈L,so dL =∅.
d0 d1 3. Find a non-trivial language L and x ∈ Σ such that dL = Lc.
Solution. Let L = {w : |w| is even} and x be any token.
If α ∈ dL then xα has even length so that α has odd length whence α ∈ Lc. If conversely α ∈ Lc,
i.e. α has odd length, we have that xα ∈ L so that α ∈ dL . Hence dx
dL = {w : |w| is odd} = Lc. dx
4. Find a non-trivial infinite language L and tokens x and y such that the Brzozowski derivatives form a non-trivial partition of L, that is, the following properties hold:
• dL ∩ dL = ∅ dx dy
• Neither dL nor dL are empty. dx dy
• dL ∪ dL = L. dx dy
Solution. Choose L = L((01)∗ + 1(01)∗). Then
dL = L(1(01)∗) and dL = L((01)∗)
and in particular, any string in dL has odd length, whereas any string in dL has even length, so
that their intersection is empty.
5. Since the Brzozowski derivative of a language is itself a language, we can define iterated derivatives
by L0 = L and Ln+1 = dLnx . x x dx
Show that for any finite language L there is some n such that Lnx = ∅.
Solution. Let L be a finite language. Let n denote the length of the longest string in L. Since
dL contains strings w such that xw ∈ L, then in the worst case, the longest string in dL is of dx dx
length n − 1. Hence, the action of taking the derivative means the longest possible string is at least one character shorter, so we can differentiate n + 1 times, and only strings of length at most -1 characters long remain, of which there are none. Hence, sufficiently many repeated derivatives of any finite language results in the empty language.
6. In analysis, one fundamental property of the exponential function ex is that d ex = ex. In analogy
to x ∈ Σ if and only if it has property P.
Solution. Suppose that dL = L. Let w ∈ L. Then w ∈ dL . Then by definition of the derivative,
then xw must be in L. (and then xxw is in L, and xxxw is in L, and so on.) So the answer is any language L that contains all of it’s strings when prefixed with x. Possible candidates (assuming x = 0) are L(0∗ ) and {11, 1, 011, 01, 0011, 001, 00011, 0001, . . .}.
7. Define a recursive function δ that – given a regular expression R – computes a regular expression δ(R) such that δ(R) = ε if ε ∈ L(R) and δ(R) = ∅, otherwise.
to that, we call a language L exponential with respect to x ∈ Σ if L = dL .
Find a property P, independent of derivatives, such that a language L is exponential with respect
δ(∅) = ∅ δ(ε) = ε
∀σ ∈ Σ, δ(σ) = ∅
δ(R + S) = δ(R) + δ(S)
δ(RS) = δ(R)δ(S) δ(R∗) = ε
8. ! A regular expression R′ is a Brzozowski derivative of a regular expression R with respect to x if L(R′) = dL(R) .
(a) Devise a rule to compute a derivative of R + S with respect to x ∈ Σ. Solution. LetL=L(R+S).
L( d(R + S) ) = {w : xw ∈ L(R + S)} dx
= {w : xw ∈ L(R) or xw ∈ L(S)}
= {w : xw ∈ L(R)} ∪ {w : xw ∈ L(S)}
= L(dR) ∪ L(dS) dx dx
d(R + S) = dR + dS dx dx dx
which fits nicely with our intuition of how the derivative operator from calculus distributes over addition.
(b) ! Devise a rule to compute a derivative of RS. with respect to x ∈ Σ. (The function δ defined above may be handy.)
(Hint: You will have to consider the cases where ε ∈ L(R) and where ε ̸∈ L(R).)
Solution. Suppose ε ̸∈ L(R). Consider
d(RS) = {w : xw ∈ L(RS)} dx
Now, since R cannot generate the empty string, it must be the case that if we partition xw into two strings, the x must come from R.
{w : xw ∈ L(RS)} = {αβ : xα ∈ L(R), β ∈ L(S)} = {αβ : xα ∈ L(R)}L(S)
= L(dR)L(S) dx
d(RS) = dRS when ε ̸∈ S dx dx
Now, consider the case where ε ∈ L(R). We could have the same outcome as before, where the x is generated from R, or R could generate the empty string, in which case
{w : xw ∈ L(RS)} = {w : xw ∈ L(S)}
and we have that d(RS) = dS . Since it could be either one of these options, we take the union,
and obtain
Concluding,
d(RS) = dR S + dS when ε ∈ S dx dx dx
dR S + dS =dx dx
ε ∈ S ε ̸∈ S
which can be more cleanly stated as
d(RS) = dRS + δ(S)dS.
(c) Devise a rule to compute a derivative of R∗ with respect to x ∈ Σ.
(Hint: Expand out the definition of R∗ and use the previous exercises to help you.) Solution. Assume that ε ̸∈ L(R).
L(d(R∗)) = {w : xw ∈ L(R∗)} dx
= {w : ∃i ≥ 0,xw ∈ Ri} ∞
= {w : xw ∈ Ri} i=0
= {w : xw ∈ Ri} i=1
as xw ̸= ε, xw ̸∈ {ε} = R0.
as L(R) has no dependancy on i, we can factor it out of the union.
by definition of R∗.
L( dx )L(R ) ∞ dR i
L( dx )L(R )
= L(dR)L(R∗) dx
Now, suppose that ε ∈ (R). Write R = ε+S, for some S where ε ̸∈ S. Then it’s clear that R∗ = S∗, and then repeat the previous argument. Hence,
dR∗ dR∗ dx = dxR
(This in particular shows that regular languages are closed under Brzozowski derivatives.)
Exercise 4 Uniqueness of Minimal DFA
!! We’ve seen in the course that the table-filling algorithm can be used to minimise the number of states
of a DFA. Prove that a DFA D obtained as an output of the minimisation algorithm is:
1. Minimal: For any other DFA E such that L(E) = L(D), the number of states that E has is greater
than or equal to the number of states D does.
Solution. (Adapted from HMU Theorem 4.26) Let D = (Σ, SD, s0, FD, δD) be a DFA obtained by the minimisation algorithm. Let E = (Σ,SE,q0,FE,δE) be another DFA with the property that L(E) = L(D). Without loss of generality, assume that SD ∩ SE = ∅ (relabelling states if required.) We define a new psuedo-DFA with two start states,
(Σ,SD ∪SE,{s0,q0},FD ∪FE,δ)
The idea is to show that if E had fewer states than D, then we can contradict the fact that all the states of D are distinguishable. Now, since L(E) = L(D), we have that δˆ(s0, x) ∈ FD ∪ FE ⇔ δˆ(q0,x)∈FD∪FE,sos0 andq0 areequivalent.
We can declare the same fact about the successor states of the starting state, for any token x, the states δD(s0,x) and δE(q0,x) are also equivalent, and the successors of those states under the same token, and so on.
Note that this psuedo-DFA is basically two separate DFA’s, as the two transition functions δD and
δE never interact with each other.
δD(s,x) s ∈ SD δE(s,x) s∈SE
Now, for any state M in D, there must exists a string w such that δˆD(s0,w) = M, as otherwise the minimal DFA D would have an unreachable state, which is a contradiction, as we could remove the state M and have a smaller DFA that recognizes the same language. Then the state δˆE(q0,w) is equivalent from M, as otherwise the DFA’s would accept different languages.
Now, for every state in D there is a corresponding equivalent state in E. Suppose E had fewer states than D. Then, by pigeon-hole principle, there must exist two states p, q in D that are equivalent to the same state in E. But then p and q are equivalent to each other, but all the states in D must be distinguishable from each other, as all equivalence states were removed by the minimisation algorithm, a contradiction. Hence, E cannot exist and there is no other DFA that has fewer states and also accepts the same language as D.
2. Unique: For any other DFA with a minimal number of states E such that L(E) = L(D), the DFAs are the same (up to renaming states)
Solution. Suppose we have two minimal DFA’s D and E (defined in the same way as above) that accept the same language. We can flip the above argument, and show that for each state pi in D there is an equivalent state qi in E, and for each state qi in E there is an equivalent state pi in D. Since minimal DFA’s have the property that no two of their states are equivalent, this provides a transformation that sends each state pi in D to it’s corresponding state qi in E.
(Hint: Recall that a minimal DFA satisfies the property that all of it’s states are distinguishable from each other (as the table filling algorithm identifies and removes indistinguishable states) and all states are reachable (as any non-reachable states are redundant and would not be present in a minimal DFA).).
Exercise 5 Optional Exercises
1. For discussion: what is the class of languages recognizable by a human (say, you)? How does that compare to the class of regular languages?
Solution. This question can get a bit philosophical. If you believe (as I do) that the human brain is nothing more than ≈ 1010 neurons firing together, and that intelligence/consciousness is merely an emergent behaviour of those neurons firing, and that there are a finite (but very large) number of states the human brain could be in, then you could (in principle) simulate the human brain with a sufficiently large DFA, so that the class of languages a human can recognize is a strict subset of the class of regular languages (as for any bound M, we can create a DFA with more than M states).
If you allow the human access to unbounded amounts of paper and pencils, then they can offload their finite memory to that paper as temporary scratch space, and simulate the action of a Turing machine, bumping the class of languages a human can recognize to at least all recursively enumerable languages.
2. !!! For experts: consider Lk = {w ∈ {0, 1}∗ : w is divisible by k when interpreted as a binary number} and find precisely those k ∈ N for which Lk is regular.
Hint. Note that DFAs can just as easily read in numbers in base 2n, by grouping bits together. You may need the fact that for every odd number c, there exists a k such that 2k ≡ 1 mod c.
Solution. Lk is regular for every k ≥ 0. For k = 0, the only number that can be written as a multiple of zero is zero, so L0 = {0}, which is finite, and thus regular. For k = 1, every number is divisible by one, so L1 = Σ∗, which is regular.
It is obvious that Lk is regular for k = 2m, for any m, as the set of all binary strings divisible by 2m is given by the regular expression
(0 + 1)00m
It is now sufficient to prove that Lk is regular for any odd prime power k = pm, we can then get any other Lk by taking intersections, which regular languages are closed under. (Example: L60=L22 ∩L3∩L5.)
We are given that for any pm, there is some k such that 2k ≡ 1 mod pm.
Define a psuedo-NFA to be a NFA that can read in an entire string of symbols on a transition. We can emulate a psuedo-NFA using a NFA below as shown, by adding dummy states.
is defined as
D1 0 D2 01 S0 S1
So it’s clear that the set of languages recognized by a psuedo-NFA is also regular.
Note that we can group the bits in the input string into blocks of length k, and in effect, the
automata is reading in numbers in base 2k. Note that
= ((2k)i i=0
= (di i=0
mod pm)(di
mod pm)(di mod pm)
mod pm)i(di
So now we only need to compute the digit sum (similar to the case for divisibility for 3 above). We draw a psuedo-NFA with pm many states for each number in the set {0, 1, . . . , pm − 1}, and then add transitions to go to the appropriate state after reading each digit in a similar fashion to Ex 1.7 Hence Lpm is regular, and thus Lk is regular for all k.
mod pm) mod pm)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com