Theory of Computation

Chomsky Classification of Grammars

According to Noam Chomosky, there are four types of grammars − Type 0, Type 1, Type 2, and Type 3. The following table shows how they differ from each...

Introduction to Grammars

In the literary sense of the term, grammars denote syntactical rules for conversation in natural languages. Linguistics have attempted to define grammars since the inception of natural languages like...

DFA Minimization

DFA Minimization using Myphill-Nerode Theorem Algorithm Input: DFA Output: Minimized DFA Step 1 Draw a table for all pairs of states (Qi, Qj) not necessarily connected directly [All are...

NDFA to DFA Conversion

Problem Statement Let X = (Qx, ∑, δx, q0, Fx) be an NDFA which accepts the language L(X). We have to design an equivalent DFA Y = (Qy, ∑,...

Non-deterministic Finite Automaton

In NDFA, for a particular input symbol, the machine can move to any combination of the states in the machine. In other words, the exact state to which the...

Deterministic Finite Automaton

Finite Automaton can be classified into two types − Deterministic Finite Automaton (DFA) Non-deterministic Finite Automaton (NDFA / NFA) Deterministic Finite Automaton (DFA) In DFA, for each input symbol,...

Finite Automaton

An automaton with a finite number of states is called a Finite Automaton (FA) or Finite State Machine (FSM). Formal definition of a Finite Automaton An automaton can be...

Regular Expressions

A Regular Expression can be recursively defined as follows − ε is a Regular Expression indicates the language containing an empty string. (L (ε) = {ε}) φ is a...

Recurrence Relation

In this chapter, we will discuss how recursive techniques can derive sequences and be used for solving counting problems. The procedure for finding the terms of a sequence in...

Mathematical Induction

Mathematical induction, is a technique for proving results or establishing statements for natural numbers. This part illustrates the method through a variety of examples. Definition Mathematical Induction is a...