Week 9

Main topic of week 9: language and regex

A brand new material starts here and of course, a lot of definitions need to remember in this week. These inclued Strings, alphabet, length, and languages. Language is a set of strings over some alphabet. It has some operations such as intersection , union, kleene star and complement.

Regular expresion are used to denote a set of language in a special structure. It is also defined in a recursive way. Which has base cases single character, empty string and empty set, and if R and S are defined regular expressions, so do R+S, RS and R*. Language which can be denoted by regular expression are defined in the same sort. Base cases are include language that can be denoted by regular expression of empty string, single charcter and empty language, and if language one and two are defined by some regular expression, the language of union and concatenation and kleene star will also be defined in the regular expression.

More example of the regular expressions are provided here, with a little alrithmetic operation we could find some regular expression are the same easily.

To prove a language denoted by regular expression is equivalent to other language, is by proving mutually inclusive, that is, the expression is a subset of the other language A, and A also can be denoted by this regular expression.