# Finite Automata Essay

1302 Words 6 Pages
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}”
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.

## Related Documents

• ###### Coal Energy Essay

Coal is a nonrenewable resource. Energy is made when the coal is burned, a machine called pulverized grinds the coal into a fine powder, then powder mixes in a boiler creating steam. Steam released from the boiler powers an engine called a turbine transforming heat into energy from burning coal in to mechanical energy that spins the turbine engine then used to power a generator. Coal is used for many different things mainly heating, cooling, cooking, transportation, farming. Wind…

Words: 1054 - Pages: 5
• ###### Linear Programming And Mathematical Optimization

Formulate the above given LPP. SOLUTION: Let us define as: x = no of TYPE A sheds produced everyday y = no of TYPE B sheds produced everyday CONSTRAINTS: Machine time: 2x+3y=0, y>=0. PROFIT : P= 60x+84y So basically the linear programming problem is to maximize P = 60x + 84y in accordance to the conditions given above .In this way , we solve a LPP . we can also represent it Graphically . Linear Programming…

Words: 4417 - Pages: 18
• ###### The Pros And Cons Of The Internet

While ubiquitous Internet access is extremely convenient and enables marvelous new applications for mobile users, it also creates a major security vulnerability—by placing a passive receiver in the vicinity of the wireless transmitter, that receiver can obtain a copy of every packet that is transmitted! These packets can contain all kinds of sensitive information, including passwords, social security numbers, trade secrets, and private personal messages. A passive receiver that records a copy of…

Words: 69202 - Pages: 277