I have always found the field of Finite Automata challenging but interesting. One of the most important applications of Finite State Machines is regular expression string matching. When I took Finite Automata at Fresno State, I had thought about implementing a graphical application for building finite state machines. My aim was just not to implement a graphical representation of the machines but also construct compact machines and perform improved string matching. Regular expressions also called pattern represent a set of strings and find their application in database and search engines. Finite Automata is an abstract but important part of Computer Science. There is still an area of regular expression matching which has not been paid enough
…show more content…
[3]
The two types of Finite State Machines covered in this project are Non-Deterministic and Deterministic. Non- Deterministic Finite State Machines (NFSM or NFA) can have more than one transitions from a state after reading the same character while in Deterministic Finite State Machines(DFSM or DFA), machines on reading a character goes to only one state. For example, a NFA after reading character ‘a’ from state 1 can go to state 2 and also state 3, but a DFA can only go to one state say state 2 after reading ‘a’.
1.4 Regular expressions
Regular expressions denote regular Languages. For example, (r1 + r2), and (r1r2) are regular expressions for languages R1 U R2 (R1 Union with R2), R1R2 (R1 concatenate with R2). Expression (a*+ b) would correspond to the language {a, b, aa, aa…}, that is the set of strings of any length of a’s and one b. A regular expression is not unique for a language. “A particular regular language can have more than 2 regular expressions for it. Similarly, there can be more than one FSM for a single regular expression. For example (a + b)* and (a*b*)* correspond to the set of all strings over the alphabet {a, b}” …show more content…
Regular expression matching is checking whether an input string is matched or accepted by a given expression. For example, a+b expression only accepts character ‘a’ or character ‘b’. Similarly, expression a*b* accepts any number of ‘a’ followed by any number of ‘b’. So, this means string aaabbb, ab, abbb, bbb, aaaa are all accepted while strings aba, bbba the ones which ends with ‘a’ after ‘b’ are not. So, if the FSMs which represent the regular expression accepts the string then, the string matches the expression else not.
1.6 Other applications of FSMs
In computer science, FSM finds its application in string matching algorithms, and language parsing. One of the strongest applications of FSM is in regular expression matching especially exact string matching. FSMs are also used in video games. In video games, FSM simulate the behavior of computer played character. The character’s behavior is represented by the machine’s states, and the transition from one state to another state corresponds to change in play or reaction of the character of the game to the surroundings.
[3]
The two types of Finite State Machines covered in this project are Non-Deterministic and Deterministic. Non- Deterministic Finite State Machines (NFSM or NFA) can have more than one transitions from a state after reading the same character while in Deterministic Finite State Machines(DFSM or DFA), machines on reading a character goes to only one state. For example, a NFA after reading character ‘a’ from state 1 can go to state 2 and also state 3, but a DFA can only go to one state say state 2 after reading ‘a’.
1.4 Regular expressions
Regular expressions denote regular Languages. For example, (r1 + r2), and (r1r2) are regular expressions for languages R1 U R2 (R1 Union with R2), R1R2 (R1 concatenate with R2). Expression (a*+ b) would correspond to the language {a, b, aa, aa…}, that is the set of strings of any length of a’s and one b. A regular expression is not unique for a language. “A particular regular language can have more than 2 regular expressions for it. Similarly, there can be more than one FSM for a single regular expression. For example (a + b)* and (a*b*)* correspond to the set of all strings over the alphabet {a, b}” …show more content…
Regular expression matching is checking whether an input string is matched or accepted by a given expression. For example, a+b expression only accepts character ‘a’ or character ‘b’. Similarly, expression a*b* accepts any number of ‘a’ followed by any number of ‘b’. So, this means string aaabbb, ab, abbb, bbb, aaaa are all accepted while strings aba, bbba the ones which ends with ‘a’ after ‘b’ are not. So, if the FSMs which represent the regular expression accepts the string then, the string matches the expression else not.
1.6 Other applications of FSMs
In computer science, FSM finds its application in string matching algorithms, and language parsing. One of the strongest applications of FSM is in regular expression matching especially exact string matching. FSMs are also used in video games. In video games, FSM simulate the behavior of computer played character. The character’s behavior is represented by the machine’s states, and the transition from one state to another state corresponds to change in play or reaction of the character of the game to the surroundings.