Category: TOC

The concept of Push Down Automata says the machine is capable of recognizing context-free languages which are supported by context-free grammar.

Table of Contents Where do we use Automata Without understanding the reason behind the concept and its importance, we always find it tough to learn. As ‘Automata Theory’ is one…

The derivation is the process of deriving or generating a language from the given production rules. The derivation is basically represented in the graphical form, which is also considered as Derivation graphs and popularly known as derivation trees or parse trees.

Context-free grammar is a model of a language. It consists of several rules. A rule defines the replacement of a symbol with another symbol. In order to generate a sentence from the language, you are allowed to apply one rule at a time. A rule does not depend on the context (hence the context freeness).

An expression that expresses the set of strings according to certain syntax rules is considered a regular expression. These expressions have certain notations which we can describe in the regular language.

Kleene Closure is the infinite set of all possible strings of all possible lengths including Ɛ It is denoted by ∑* So ∑*=∑0 U ∑1 U ∑2 U ∑3U….. For example over ∑= {0,1}.
Kleene star (or Kleene operator or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters.

Avram Noam Chomsky (born December 7, 1928) is an American linguist, philosopher, and cognitive scientist who has given the hierarchy of grammar in Theory of Computation. Hierarchy means an organized structure in which items are arranged according to their rank or level. Chomsky has proposed such kind of hierarchy in which he has given different levels to grammar.

To understand the concept of the Theory of Computation, students need to understand some basic mathematical concepts through which they can understand how Computer computes and how compiler design.

Finite automata is classified into two parts Deterministic and Non Deterministic Automata, which are in short considered as DFA and NFA. In this article we will understand the concept of DFA and NFA with its Comparison.

Regular languages are a subset of the set of all strings. which are used in parsing and designing programming languages.

Automata Theory is a branch of computer science that deals with designing abstract computing models having a sequence of operations. With the help of that model, it will be easy to write algorithms and convert them into machines.

Before we move to the Theory of Automata, we should have a basic understanding of some terminologies which are frequently used like Symbols, Alphabets, Strings, and Languages.