week.nine

reminder: test #2 on friday!

on monday, we started on yet another brand new topic. unfortunately, i was late to class, so i got in time when they had moved on to the operations on language. i didn't know what language was (formally), so i had a hard time keeping up with the rest of the lecture. but here's what i know about languages so far: it's actually a set; of string; over an alphabet (which is also a set, but only consists of singular symbols like {"a", "b"} or {"0", "1"}). the examples are done heavily on binary strings which only has two symbols {0, 1} so it makes it easier to follow in class than having the entire english alphabets. we then talked about regular expressions, which are closely related to the notion of language - regular expression can denote almost any language (some languages are impossible to denote with regular expressions). regular expressions themselves have a set of operations that can be applied to represent a complex regular expression: alternation (union), concatenation, and the kleene star. alternation and concatenation do what you expect them to do - either/or, and combining two regexes (order matters), respectively. the kleene star behaves in a way that it repeats its preceeding subexpression zero or more times (so the empty string also belong to the language denoted by a regex involving a kleene star). i'm really glad to have a whole topic dedicated to regexes because i ahve come across it in my 207's a1 starter code and i didn't have a clue what it was. and we are also touching on this topic in 207 as well - so it helps either way.

on wendnesday, we continued on with regular expressions. prof. heap started off with some example and asked us what language each regex on the slide denotes. i, ahem, got to class late again. consequently, i had a hard time distinguishing all from each other because they all look the same to me haha. but as the class progresses, it became clear to be the importance of brackets as logical grouping so operation like the kleene star can be applied to it. prof heap also showed us how to prove the equivalence of a language and a language denoted by a regex. this is done via mutual inclusion because languages are sets so to prove two languages are equivalent is the same as proving that they are subsets of each other. as it turns out, this principle is crucial in proving languages. even proving equivalence requris this property of a set because to prove that two regexes are equivalent is the same as proving that the languages they each denote are equivalent.

on friday, we had our second term test. i thought it wasn't all that bad. i did choke in proving the last question tho - downward() method. i guess i was still unclear about proving partial correctness and termination, and on top of that finding a suitable loop invariant. i wish someone would clarify that for me...i regret that i was late for most of the week this week because i think the times i were late the the most crucial times in understanding complex languages like regular expression in depth.