week.twelve

reminder: assignment 3 due friday!

on monday, we learned a proving technique to prove that some regexes are impossible to be denoted by a language (such as the language that consists of the the same number of 0s and 1s. what prof heap did in the lecture look too overwhelming for me, so i am going to have to refer the course text to bette understand it. but i'm really hoping that it won't be on the test, nor in the exam - especially the fact that it involves proof by contradiction to prove such a language isn't regular.

on wednesday, we learned about a new topic on context-free grammar, which derives a lot fo its principles similar to those of a fsa. cfg does what a fsa can't do - denote an infinite language, which means that it is non-deterministic. it has a properties similar to a dfsa, namely the quadriplet G = (V, \sigma, P, S), where V is a set of variables, \sigma is a set of terminals, P is a set of production, S is the start symbol. it is good to note that V and \sigma are disjoint, and terminals work as "rules" that tells you what you "may do so", rather than "must do". the diagramatic representation of a cfg is like those of a dfsa, only there aren't any nodes, and the arrows lead to one or more (combination of) variables and terminals (due to the non-deterministic characteristic of a cfg). prof heap also showed examples of languages denoted by cdf that consists of binary strings with even number of 0s and 1s, as well as one that contains matching parentheses. it is clear how grammars can denote an infinite language because of the property that a variable can produce a variable infinitely many times as we wish (kind of like how recursion works).

on friday, we went on to proving the correcteness of the cfg that denotes the language of strings with the same number of 0s and 1s. the proving involves sort of the equivalent of state invariants, but for cfgs, denoted S =>* \alpha, which means that strig \alpha is derived from S thorugh a number of productions. i had no problem keeping up with the fsas, but this topic in particular i thought was closely related to fsas, but it turned out to be a whole other dynamic in denoting a language - and now i'm having troubles keeping up and catching up with the materials. i will try to read on them i the text nad hopefully be ready for them in the exam. also, the last assignment was due tonight, which i thought was quite challenging, but easy once i get on the rhythm of it. and question 4 seemed hard on the outside, but it's pretty simple once i figured out the machines for both languages - it's only a matter of combining the two through means of cartesian product. all in all, it was the first assignment that i actually spent time on doing - so that must count for some effort, right?