The Pumping Lemma for Regular Languages Pumping Lemma is a powerful tool to prove that a language is not regular. The proof technique used here is Proof by Contradiction. ie., initially, in the proof, the language is considered as a regular language. The following table shows how and where pumping lemma used exactly: The finite […]

## Posts in category Theory of Computation

## Turing Machine: Acceptor & Trans...

We have studied two types of languages from the Chomsky hierarchy: regular languages and context-free languages. These languages can describe many practically important systems and so they are heavily used in practice. They are, however, of limited capability and there are many languages that they can not process. Here we are going to study the […]

## Automata Theory: An Introduction

Automata Mathematical representation of formal language (FL) is known as automata. Automata theory is a subject which describes the behavior of automatic machines mathematically. In Computer Science the word automata is used for recognizer or acceptor as well as transducer (machine with output capability). Types of Automata: There are four types of automata: Finite Automata (FA) […]

## Chomsky Classification of Grammar

Phase Structural Grammar A language L is set of Valid strings over ∑ where ∑ = alphabet or Character set. ∑* is set of All Possible strings using ∑ in which some strings are valid and others are not valid. Thus, There should be some mechanism to check if a given string is valid or not. The number […]

## NFA: Non-deterministic Finite Automat...

Nondeterministic means choice of moves for automata. In non-deterministic finite automata we are allowed a set of possible moves. The definition of nondeterministic automata is similar to that of deterministic finite automata but with one difference, the transition function. The language accepted by a NFA is regular just as in case of a […]