Concatenation on Σ* is associative, i.e., X(YZ) = (XY)Z for every X,Y,Z ∈ Σ*
The following is a summary and reflection upon the work I did as part of ICS641: Advanced Theory of Computation. The course meets once a week for 3 hours. There are only 4 grad students in the course.
While I knew a learning portfolio was required for this course, I did not realize what we were required to do for it until Week 5. So the first few weeks here are just a recap. (Thanks to classmate Anthony Christe for the pictures for those weeks!)
For each week, I'll usually explore one of the more interesting proofs or exercises we did in more detail.
On the first day, we covered some course details and then jumped right into alphabets, semi-groups, and monoids. We were asked to prove the following:
Concatenation on Σ* is associative, i.e., X(YZ) = (XY)Z for every X,Y,Z ∈ Σ*
Solving this required the definition of string equality:
So, we broke X, Y, and Z down into their component parts:
X = <a1, a2, ... ai>, Y = <b1, b2, ... bj> Z = <c1, c2, ... ck>.
We then showed the different concatenation orders produced the same final string of a, b and cs.
I hadn't really done any proofs since 10th grade geometry, so this was quite a challenge. Luckily, we were able to work in pairs.
We covered strings, languages, lexographic ordering, Kleene closures, phrase structure diagrams. The proof we did was:
Lexographic ordering is transitive. That is, if x ≤ y and y ≤ z, then x ≤ z.
This required using the definition of lexical ordering, which is paraphrased as:
If a ≤ b, either: • a is a prefix of b (and so a comes first), or • a and b share a common prefix up to a common point i in the two strings, and the symbol at ai+1 is < the symbol at bi+1.
Since this means there are two cases by which x could be ≤ y and two cases by which y ≤ z, the proof required four cases. We only had time for a couple of these cases. As in Week 1, we broke X, Y, and Z into example symbol sequences and compared them that way:
As another exercise, we were given an expression and were then asked to show how it was derived from a given grammar.
We covered regular sets, regular grammars, and finite automata. We had to prove or disprove the associativity of Kleene closure: (X(YZ)*)* = ((XY)*)Z). This was disproved using a proof by counter-example.
Given Σ = {a, b}, we built a DFA to accept the language L = {w ∈ Σ* | consecutive as do not come before consecutive bs}
We also wrote a regular grammar for decimal numbers between 0 and 1 exclusive, a DFA that accepts any string of {a, b}* that does not contain {aaa}, and an NFA that accepts any string of {a, b}* whose third-to-last symbol is a b.
We continued to cover regular sets, regular grammars, and FAs.
We had to write a regular expression for all strings over {a, b, c} that do not contain {aaa}. (I didn't notice at the time how similar this was to last week's DFA problem!) I came up with the following:
(b|c)* (a|aa|((a|aa)(b|c)(b|c)*)*|ε)
So this means the string might start with any number of bs and/or cs. After this optional prefix, if there are any as, then it's either 1 or 2 by themselves, or 1 or 2 followed by at least one b or c. This sort of combination could be repeated. The string could also be empty.
We also produced a finite automata for a given regex and then converted a machine to a regex. I found this last to be quite challenging and didn't fully manage it.
This week, we converted an NFA with ε-moves to one without. We walked through proofs of equivalence of a regular set to finite automata and of a finite automata to a regular set. We also learned about the pumping lemma.
We had to prove or disprove that {0m1n0m+n | m >= 1 and n >= 1} is a regular set. We disproved this by breaking the problem into several cases.
For our first assignment, we will have to write a formal proof. We will get to choose between 3 problems of different difficulty levels. Today we learned what is likely to be the standard problem:
Prove either that the following is a regular set, or that it is not:
{xxRw | x, w in (0 + 1)+ and xR means x written in reverse}
So x and w are both strings made up of one or more 0s and 1s in any combination.
I've learned in class that the first step to a proof is to try to form some intuition as to what the answer is. Often, this is fairly obvious. My first thought here was to see if I could produce a regular grammar for this set of strings (which is to say, language). Regular sets, regular grammars, regular expressions, and finite automata all describe/accept/produce the same class of languages. So, if I can produce a regular grammar for this language, I know it's also a regular set.
A regular grammar contains only production rules in the following forms:
B -> aC B -> a B -> ε
where a is terminal symbol, B and C are non-terminals, and ε is the empty string. This is an example of a left regular grammar, since in aC, the terminal is produced to the left of the non-terminal.
In the margin of my handout, I sketched the following:
S -> W0 S -> W1 W -> W0 W -> W1 W -> 0Z W -> 1N Z -> X0 N -> X1 X -> 0Z X -> 1N X -> ε
So, S produces at least one 0 or 1. W can continue to expand as 0s or 1s. Then, W transitions to X, starting with 0Z or 1N (since we need 1 or more symbols for each x string). For each 0 or 1 produced on the left, a matching one is produced on the right side of the non-terminal. This builds up mirrored x and xR from the middle. Eventually, the X non-terminal can be dropped using the final production rule.
So, it looks at this point that this is indeed a regular set. However, this means I should also be able to create a regular expression to describe the same language... but I could think of no regular expression that lets me match pairs of characters either inwards to or outwards from the middle of a string as I did in the grammar above. So something fishy is going on...
Reviewing the definition of regular grammar (which I couldn't quickly find again in my notes or readings, so thanks to Wikipedia), I realized that the above grammar is NOT regular. A regular grammar is either left regular or right regular, but what I have above is a mixture of the two. That makes it a linear grammar.
Since I cannot produce a regular expression or regular grammar for this set, I am now fairly confident that it is not a regular set. I will set out to prove this using the pumping lemma.
We first covered closure properties of regular sets. A set is closed on some operation if the results of that operation are also in the set(s) that went into the operation. These operators included union, concatenation and Kleene closure (from the definition of a regular set). Also: complement (this was a little surprising to me), intersection, substitution (of single members by a set), homomorphism (a substitution with only a single alternate rather than selected from a set), inverse homomorphism, and quotients. (It takes a little getting used to thinking of multiplication, division, and exponent operations on strings.)
We did a proof to show whether the following operation of removing every second (even) symbol is closed or not:
f(L) = {a1, a3, a5... a2n-1 | a1, a2, a3, a4... a2n}
Conjecture: Class of regular sets is closed under f.
Proof: Let L be an arbitrary regular set. Since every regular set is accepted by a DFA M, suppose that M = (Q, Σ, δ, q0, F) such that L(M) = L. We can then construct M' = (Q', Σ, δ', q'0, F') where:
Q' = Q' ∪ {qf} where qf ∉ Q
δ' = {s | s = δ(δ(p,a), b) for b ∈ Σ} ∪
{qf | δ(δ(p,a), b) ∈ F for b ∈ Σ}
q'0 = q0
F' = {qf}
Not quite clear from above is that M' in an NFA. Also, it seems now that we didn't qualify what a is when defining δ'. But the idea here is that, for each second input b, we get the set of all states reachable with the sequence ab in the original M, plus a new single final state we added to M' if the sequence reached a final state in M.
This proof is not quite done yet, though. We now have to prove that M' accepts L' (the shortened language). We could do this with a proof by induction, showing that M' gives nothing on a empty string and that, given a sequence of length k, it produces k+1.
We also lightly covered some decision problems regarding FAs and then stepped through what turned out to be a fairly complicated algorithm for minimizing an FAs based on equivalence classes.
I gave a little more thought to the A01 problem and proving that it is not regular:
{xxRw | x, w in (0 + 1)+ and xR means x written in reverse}
I'm troubled by the fact that I can pump this by pumping w. I'm guessing the secret somehow lies in the 3rd clause of the pumping lemma... I'll have to think more on this when it's not 11:30pm.
Other reading suggested a very different approach: if regular sets are closed on a particular operation, what if you can show that L' is produced from L by an application of one of those operations? If L' is known not to be regular, then L have must not be regular either.
Today we covered context-free languages, focusing on context-free grammars. I learned that some languages are inherently ambiguous so that it is impossible to produce a non-ambiguous CFG for them.
We did a number of small grammar exercises. I enjoyed these--they were just challenging enough to be interesting but not daunting.
We produced an example of an ambiguous CFG. In my experience so far, this simply seems to come from having at least one non-terminal that leads to two or more possible productions.
We also produced a grammar for the language of balanced parentheses. Then we performed a left-most, right-most, and parse tree derivation of a given string in a given language. I found that starting with the left-most derivation worked pretty well, and this derivation served to produce the parse tree. The tree was then very helpful to determining the correct right-most derivation. I'm not sure yet if this is the best course of action in general.
We wrote a grammar for the language of regular expressions, and then thought about how to write a grammar that produces simple math expressions without any unnecessary parentheses.
Finally, we wrote a grammar for the language of {a,b}* such that each string contains twice as many as as bs. My solution:
S -> SS | S S -> aSab S -> aaSb S -> aSba S -> abSa S -> bSaa S -> baSa S -> ε
The idea here is that each normal production produces 2 as for every b, but the symbols can be in any of the possible orders. The expression can then be expanded in the middle or, thanks to the first production rule, on either end.
The question that remains is proving that this actually produces all the strings in the language and not only some subset. I would like to ponder on this more, but I'm currently trying not to get sidetracked from A01!
This week we covered push-down automata (PDAs) and their equivalence to context-free grammars (CFGs). We learned about equivalent forms of CFGs: Chomsky normal form (in which every rule leads to a production of either two non-terminals or one terminal) and Greibach normal form (in which every rule leads to a production which begins with one terminal followed by 0 or more non-terminals). This GNF form forces a left-most derivation.
Our first exercise was to produce a PDA that accepts palindromes. Then we paired up to prove that the class of languages accepted by PDAs using a final state is equivalent to the class of languages accepted by PDAs by any empty stack. Anthony and I set out to prove that any final state PDA can be duplicated with an empty stack PDA, as follows:
Given a final-state-based PDA, M=(Q, Σ, Γ, δ, q0, Z0, F),
an empty-stack-based M' can be constructed such that:
Q' = Q ∪ {qs, qf | qs, qf ∉ Q}
Σ' = Σ
Γ' = Γ ∪ Ze
q0' = qs
Z0' = Ze
F' = F [though these are ignored in M']
δ' = δ ∪
{(q0, ε, Ze) -> (qs, Z0Ze)} ∪
{(q, ε, Z) -> (qf, Z) | q ∈ F, Z ∈ Γ} ∪
{(qf, ε, Z) -> (qf, ε)}
The idea here is that we added a new start state (qs) and a new final state (qf) that were not originally in M's states. Then we added a new stack symbol (Ze) that we add to the stack before transitioning to M's original start state. This way, the stack can never become empty during M's normal processing: it will simply reveal this special Ze symbol. Then, for any final state in M, we transition to our new final state qf and continue to pop the stack until it is empty.
This was a fun proof. However, I did learn that, since δ is a function, we should not use set notation as we did here. Instead, we should have done something like this:
δ'(q, a, Z) = δ(q, a, Z) if q ∈ Q, a ∈ Σ, Z ∈ Γ
{(qs, Z0Ze)} if q = q0, a = ε, Z = Ze
{(qf, Z)} if q ∈ F, a = ε, Z ∈ Γ
{(qf, ε)} if q = qf, a ∈ Σ, Z ∈ Γ'
∅ otherwise
The format of the "otherwise clause" is my own device though; I'm not sure if that would be legal. And of course, the proof is still not quite done: we would also need to prove L(M) = L(M').
We ended class by converting a short grammar to CNF.
Luckily we got an extension on A01. I'm nearly there! I've chosen to work with the string (01)n(10)n1. I can limit the adversary to pumping only the initial (01)n portion of the string. However, after the pumping, the adversary can "redraw" the xxRw boundaries. I can show that the pumping must have occurred in x (which is no good for the adversary) or on the boundary between xxR. This last is the real cornerstone of the puzzle... but I haven't quite figured out yet how to show that there is no way to produce a valid xxR this way. I know the solution involves the reflection point between x and xR. I can show it works for even length vs, but I'm having a hard time with odd lengths.
We started class with an application of the pumping lemma to a context-free language. We did this as a group. This was a little different than for regular grammars, since the range of the pumped substring is not limited the left-most side of the original string. It took us 5 different cases to show that {aibjck | i < j < k} is not context-free. We had to consider when the pumping range includes only as, only bs, only cs, as and bs, or bs and cs. For the last two cases, there was an interesting possibility that pumping (for example) a series of as and bs would result in a string in which not all the as were consecutive, and thus not in the original language.
We briefly reviewed Ogden's Lemma (a variation of the pumping lemma for CFLs), closure properties, and decisions regarding CFLs.
Our next exercise was to show that CFLs are closed under reversal. That is: LR = {wR | w ∈ L}. Though I originally considered a PDA approach to this proof (trying to use the stack in some way to reverse the string), I then remembered that any CFG can be written in Greibach Normal Form where there is only one terminal per production. It should then be possible to just reverse the form of all the rules to give a right-most derivation of the original left-most derived string. I stumbled a bit on how to phrase this rigorously. The trick was to just use R and Kleene closure when discussing the productions. Thus:
Let L be an arbitrary CFL. There must be a CFG G=(V, Σ, P, S) such that L(G).
Construct a CFG G'=(V', Σ', P', S') such that L(G') = L(G)R = {wR | w ∈ L}.
By Theorem 4.6 (Hopcroft and Ullman), we can assume, without loss of generality,
that G is in Greibach Normal Form, and so all rules in P are of the form:
A -> aα, where α is a series of 0 or more non-terminals. (That is, a ∈ V*)
Thus:
V' = V
Σ' = Σ
P' = {A -> αRa | A -> aα ∈ P for a ∈ Σ and α is in V*}
We discussed that this was not yet sufficient, and that we must now show that this grammar produces LR. This could be done with a proof by induction based on the number of rules applied.
To finish up, we traced the CYK algorithm together as a group. This algorithm solves the membership decision problem of telling you whether a given string is produced by a given grammar.
I started doing some research for the paper part of A01 and some of the proofs regarding palindromes gave me some insights into my own problem. I reformatted my chosen string so that the two symmetrical parts are identical except for the transition point. It all came together after that! More next week once the paper is done.
I spent most of this week on my paper. I finally realized that I was wrong: I couldn't use pumping lemma alone to prove this language non-regular.
I considered using closure properties as well, but I wasn't sure if I could do that. Specifically, it has been proven that a regular set concatenated with a regular set must also be a regular set. But does it then necessarily follow that dividing a set into a regular and a non-regular set means the original set was also non-regular? In the end, I chose to use the Myhill-Nerode theorem instead.
Learning LaTeX proved to be fairly painless, though I still need to work on the details of BibTex. I can certainly see why people like LaTeX for math papers--once you get over the learning curve. I can see too that writing formatting classes would make this a really powerful system. I'm a long way from that point, though!
I finally finished my paper and slides about 1am the night before class. (I found a small error in my proof a little after midnight, and so I had to touch things up a bit in both the paper and slides.)
We presented our papers in class. It went fairly well, though I always find PowerPoint slides take a lot of rehearsing to present smoothly--which is to say more rehearsing than I did this time. Others used closure properties with the pumping lemma to prove the same language non-regular. I liked Boa's ordering of the logic: Since we assume the language is regular at the start of the proof, we can logically apply regular closure properties to it without hesitation. If a contradiction results after breaking the problem down, we still know the contradiction must be due to our starting assumption about the entire original language.
Overall, the experience of writing this paper was very much like preparing and presenting at a conference.
We still had an hour of class time left, so we learned the basics of Turing machines (TMs). We started constructing one that recognizes palindromes but ran out of time.
This week we started by putting our palindrome-recognizing Turing machines on the board. I then had to convert mine to recognize wwRx, which I did by using a nondeterministic Turing machine.
I learned the difference between total functions and partial functions. In a total function, f(x), every value for x in the domain maps to some valid function result. In a partial function, the function is undefined for some values of x. Total Turing machines represent total functions and will so always eventually halt for any given input. This corresponds to a recursive set or a decidable language. On the other hand, a general Turing machine may represent a partial function, meaning it will halt (neither accept or reject) on some input. This corresponds to recursively enumerable sets and Turing-recognizable languages.
We learned of a number of Turing machine variants, including mulititrack, multitape, checkmark, shifting, subroutine, non-deterministic, and multi-dimensional. Amazingly, all of these can be converted to a regular deterministic TM.
A TM fills three roles: recognizing a language, computing a function, or enumerating a language. Since we've already seen a lot of finite automata recognizing languages, we had a look at an example of each of the other two problem types. As exercises, we designed a TM that multiplies two positive integers and another that enumerates all positive integers.
We learned about decision problems: determining whether the input satisfies a particular property and reporting yes if it does or no otherwise. The Halting Problem is the first undecidable problem found: Given a description of a TM, will that TM halt on all input?
No class (Good Friday).
This week, we covered a lot of material with fewer exercises. Dr. Sugihara recommended we read Gödel, Escher, Bach, which I've heard good things about before. It's on my list.
We learned about universal TMs, which can accept both a description of a TM and input and simulate the given TM on the input. We discussed undecidability again, and the correlation between decidability and recursive functions and undecidability and recursively enumerable functions. We learned about the Post Correspondence Problem as a classic example of an undecidable problem--like the halting problem, only simpler. It can be used to prove other problems undecidable.
Returning to decidable problems, we explored computation complexity in terms of both space and time and for deterministic and nondetermistic solutions. Savitch's theorem showed an interesting relationship between these: that if a nondeterministic TM can solve a problem using a given amount of space (f(n)), then a deterministic TM can solve the problem using only the square of that space, (f(n))2. So relying on nondeterminism does not drastically reduce the required space constraints.
We looked at the relationships between the overlapping sets of problems: P, NP, and PSPACE, as well as NP-Complete and NP-Hard.
Today we continued with an exploration of NP-Completeness. We saw how the Max Clique problem maps to the 3-SAT Boolean satisfiability problem in such a way that shows that the Max Clique problem must also be NP-Complete. We then completed an exercise where we produced an equivalent mapping between the Hamiltonian Cycle and Boolean Satisfiability problems. This was both abstract and challenging. We ended up working on it together as a class.
We learned about oracle TMs, which are assumed to be capable of asking God for an answer. Such machines would be able to overcome certain undecidable problems, but they still from their own hierarchy of undecidable complexity classes.
We concluded with the relationships between P, NP, and co-NP.
This week was a big push to finish my second paper. Last week, I found an online resource that provided a version of the grammar I needed and the key insight I had been missing. Although I then set that solution aside, wrote my own solution from scratch and cited the source as my inspiration, I started to wonder if perhaps I'd still overstepped a line here. I emailed Dr. Sugihara and confirmed that there was enough other content in the paper--particularly a proof that the language produced by the grammar was equivalent to the original language--that it was okay. Still, it was one of those disturbing "dark knowledge" experiences: sometimes you learn something that taints you but that you can never unlearn it.
The LaTeX process went very smoothly this time. However, after a few interruptions, I still found myself finishing up my paper and presentation at 3am. I'm getting too old to run on 3 hours of sleep! I was trying to form a more rigorous proof regarding all even-length strings in L being derivable from the grammar. Specifically, I was hoping to use proof-by-induction to show that any combination of Z-Z pairs could be generated by the grammar. In the end, I did a bit of 2am hand-waving back to some of my earlier arguments (which were pretty solid). This argument still seemed to hang together well enough under dawn light, though, so I guess I did alright.
I think my slides and presentation came together a little better this time. However, I wish I'd had time for one more careful proofreading of my paper.
Today concluded ICS641. We presented our papers, completed a course evaluation, and ended early. It was a beautiful day outside.