Now we will discuss regular languages in this post.
Regular language:
A regular language is the set of strings generated by a regular grammar. Regular grammars are also known as Type-3 grammars in the Chomsky hierarchy.
A regular grammar can be represented by a deterministic or non-deterministic finite automaton. Such automata can serve to either generate or accept sentences in a particular regular language. Note that since the set of regular languages is a subset of context-free languages, any deterministic or non-deterministic finite automaton can be simulated by a pushdown automaton.
Now you will be curious to know about the terms “deterministic finite automaton”, “non-deterministic finite automaton”, “pushdown automaton” and “context-free languages”.
In next Post, we will discuss only “deterministic finite automaton” and “nondeterministic finite state machine”.
Showing posts with label automaton. Show all posts
Showing posts with label automaton. Show all posts
Tuesday, May 1, 2007
Monday, April 23, 2007
Automata Step by Step
I am writing this blog for the people who are strongly interested in Automata and Formal languages or who want to start from basics of Automata.
First of all, we will discuss some very basic definitions of Automata. In Automata theory, all things are related to each other so you will notice that you need definitions of other words for understanding a particular definition. We will also see formal definitions of all terms after understanding their basic definitions. After basic and formal definitions, we will solve a lot of good “Problems of Automata” and see a lot of good examples.
Basic Definitions:
If you are a beginner, you should know what is Automata and Automata theory.
1. Automaton:
In Simple Words, An automaton (plural: automata) is a self-operating machine. The word is sometimes used to describe a robot, more specifically an autonomous robot. Used colloquially, it refers to a mindless follower.
An automaton is a mathematical model for a finite state machine (FSM). An FSM is a machine that, given an input of symbols, 'jumps' through a series of states according to a transition function (which can be expressed as a table). In the common "Mealy" variety of FSMs, this transition function tells the automaton which state to go to next given a current state and a current symbol.
2. Automata theory:
Automata theory is the study of abstract machines and problems they are able to solve. Automata theory is closely related to formal language theory as the automata are often classified by the class of formal languages they are able to recognize.
Now at this point, it is important to know about Finite state machines.
3. Finite state machine (FSM):
A finite state automaton (plural: automata) is a model of behavior composed of a finite number of states, transitions between those states, and actions.
4. States:
A state is a unique configuration of information in a program or machine. It is a concept that occasionally extends into some forms of systems programming such as lexers and parsers.
We will see the definition of parser in the next post. Above 4 definitions are enough for today. Please don’t forget to review them otherwise you will not be able to understand the next post. Read carefully. Have a good day.
First of all, we will discuss some very basic definitions of Automata. In Automata theory, all things are related to each other so you will notice that you need definitions of other words for understanding a particular definition. We will also see formal definitions of all terms after understanding their basic definitions. After basic and formal definitions, we will solve a lot of good “Problems of Automata” and see a lot of good examples.
Basic Definitions:
If you are a beginner, you should know what is Automata and Automata theory.
1. Automaton:
In Simple Words, An automaton (plural: automata) is a self-operating machine. The word is sometimes used to describe a robot, more specifically an autonomous robot. Used colloquially, it refers to a mindless follower.
An automaton is a mathematical model for a finite state machine (FSM). An FSM is a machine that, given an input of symbols, 'jumps' through a series of states according to a transition function (which can be expressed as a table). In the common "Mealy" variety of FSMs, this transition function tells the automaton which state to go to next given a current state and a current symbol.
2. Automata theory:
Automata theory is the study of abstract machines and problems they are able to solve. Automata theory is closely related to formal language theory as the automata are often classified by the class of formal languages they are able to recognize.
Now at this point, it is important to know about Finite state machines.
3. Finite state machine (FSM):
A finite state automaton (plural: automata) is a model of behavior composed of a finite number of states, transitions between those states, and actions.
4. States:
A state is a unique configuration of information in a program or machine. It is a concept that occasionally extends into some forms of systems programming such as lexers and parsers.
We will see the definition of parser in the next post. Above 4 definitions are enough for today. Please don’t forget to review them otherwise you will not be able to understand the next post. Read carefully. Have a good day.
Subscribe to:
Posts (Atom)