I dont know if it is composed to be so, there is one week we had two courses, CSC207 and CSC236, both talking about regex. 207 was taking a more practical approach leaving questions to design interesting regexes that fit some specific strings. Being a course on computational theory, 236 was more theoretically oriented on this topic. Here we started from a set of symbols, that is an alphabet, denoted as \sigma. The set of all string over \sigma is denoted as \sigma*. A language, denoted as L, is a subset of \sigma*. Intuitively, a language is just a set of strings over alphabet \sigma, which is actually true even for English or Chinese if one think about it. L can have various operations, the most interesting being Concatenation and Kleene star. I now jump to regex. A set of regexes is inductively defined:
Basis: \empty, \sigma and a(for each a \in \sigma) belong to RE.
Induction Step: If R, S belongs to RE, then (R + S), (RS), R* belong to RE.
This definition provides that a lot of proves regarding regexes will be a structural proof base on that.
Proving a regex R represents a language L:
This kind of question is worth noticing since we have to prove both ways. 1: L(R) is a subset of L, which should be done by analyzing the Regex, and 2: L is a subset of L(R), by carefully chop the strings in L into segments so that can fit by R.
Subscribe to:
Post Comments (Atom)

No comments:
Post a Comment