Progress over Perfection

Posts in category Theory of Computation

The Pumping Lemma for Regular and Con...

The Pumping Lemma for Regular and Context-free Languages

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 […]

Turing Machine: Acceptor & Trans...

Turing Machine: Acceptor & Transducer

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 […]

Ambiguity and Simplification Algorith...

Ambiguity and Simplification Algorithms of CFG

Ambiguity in CFG A CFG G is ambiguous if there is at least one string w in L(G) having 2 or more derivation trees. example: Let CFG G : S → S + S | a The string a + a + a ∈ L(G) has 2 left most derivatives as shown below, so given G is […]

PDA: Push Down Automata Designing

PDA: Push Down Automata Designing

PDA from CFL L = {anbn > 0} Accepted strings = {ab, aabb, aaabbb, …} δ(q0, a, Z) = (q0, aZ)   // q0 is the initial state, a is the current input symbol and Z is the top of the stack then push a in the stack δ(q0, a, a) = (q0, aa)   // q0 is the […]

Automata Theory: An Introduction

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

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...

NFA: Non-deterministic Finite Automata Programming

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 […]

Closure Properties of languages

Closure Properties of languages

Closure: When you combine any two elements of the set, the result is also included in the set. Closed under union – what does it mean? Suppose we have a language L and a language S and both are context- free. We know that the union of  2 context- free languages is also context free (See […]


July 2018
« Apr