on monday, we learned about a paper-and-pencil machine called the deterministic finite state automata. what it is essentially is a way to represent a language that a egular expression can't (as such the intersection of two languages, which is not impossible to do but would take a longtime to derive). a dfsa machine consists of the quintiple M = (Q, \sigma, \delta, s, F), where Q is the set of states in the machine (and is finite), \sigma is the set that contains the alphabet the machine will go over, \delta is the transition function where it takes in an ordered-pair of a state from Q and a symbol from \sigma and it returns a new state (may be the same state), s is the starting state, and F is the set of acception states (a subset of Q). in class, prof heap showed us an example of a language that consists of all strings that have even 0s and even 1s, and is denoted by a dfsa. it is interesting to see something new like an automaton because i have never come across any before, and the fun goes to determining where each labelling edge transitions to, given a state and an input symbol. although, i'm still blurry with my language operations (let alone regexes), i think i would have more fun with constructing automata than analyzing a bunch of 0s and 1s.
on wednesday, we continued on with our machine that accepts binary strings with even 0s and 1s. in particular, we elaborated the transition function and deriving the extended transition function from it, which works almost the same way as the transition function, only instead of taking in an input symbol, it takes in a string, and the it returns a state. in short, \delta*(q, x) = q' means the string x takes the dfsa machine from state q to q'. in a sense it works like a patch where the characters of the string (from left to right) is a labelled edge, forming a path, from state q to the state q'. the extended transition function is also used in proving that a dfsa works by means of state invariant, where the function starts from the starting state and reads in a string to one of the states in the machine - the state invariant indicates what is true about the string when it enters that particular state. we then moved on to designing a dfsa - one that accepts binary strings that are multiple of 3 in base 2. it turns out that the key idea in designing this dfsa is the left-shifting of an binary number. when x is a binary string, the concatenation x0 simply doubles the binary number's value in decimal form, and similarly x1 doubles and adds 1 as the decimal of that binary number. i thought this experimenting of designing a dfsa is particularly interesting because it utilizes the 0s and 1s characters of binary numbers to cater to the course's convention of using the alphabet {0, 1}. i don't find this topic more challenging than, say, proving iterative correctness because the fun goes into thinking about the state invariants and performing a trial and error conducts to determine where each symbol leads a state to another.
on wednesday, we continued on with our machine that accepts binary strings with even 0s and 1s. in particular, we elaborated the transition function and deriving the extended transition function from it, which works almost the same way as the transition function, only instead of taking in an input symbol, it takes in a string, and the it returns a state. in short, \delta*(q, x) = q' means the string x takes the dfsa machine from state q to q'. in a sense it works like a patch where the characters of the string (from left to right) is a labelled edge, forming a path, from state q to the state q'. the extended transition function is also used in proving that a dfsa works by means of state invariant, where the function starts from the starting state and reads in a string to one of the states in the machine - the state invariant indicates what is true about the string when it enters that particular state. we then moved on to designing a dfsa - one that accepts binary strings that are multiple of 3 in base 2. it turns out that the key idea in designing this dfsa is the left-shifting of an binary number. when x is a binary string, the concatenation x0 simply doubles the binary number's value in decimal form, and similarly x1 doubles and adds 1 as the decimal of that binary number. i thought this experimenting of designing a dfsa is particularly interesting because it utilizes the 0s and 1s characters of binary numbers to cater to the course's convention of using the alphabet {0, 1}. i don't find this topic more challenging than, say, proving iterative correctness because the fun goes into thinking about the state invariants and performing a trial and error conducts to determine where each symbol leads a state to another.
on friday, the problem set was due. i didn't find it particularly difficult mainly because it deals with finite number of strings. here's to hoping for good marks. we designed yet another dfsa hat accepts a binary string that includes the (sub)string 110. it's important to note that because this machine accepts a substring, any input symbols that are read after it has accepted that particular substring will be accepted regardless until the whole string is finished being inputted. furthermore, after the machine land onto the accepting state, that state also works as a trap state - any substring after 110 will transition into the state. this was another good case showing the ability of a dfsa to accept a substring, rather than a string as a whole. i don't think it was as challenging as designing a machine as yesterday's.
No comments:
Post a Comment