Theory of Computation

We learn about the halting problem in computability theory. It is as follows, Given an algorithm and its initial input, we determine if the algorithm when executed in this input will ever stop/halt. If it does not halt, it runs forever in an infinite loop.

In this article, we learn about the properties of recursive and recursively enumerable languages in terms of union, intersection, and complements and compare the two languages.

We learn about non-deterministic turing machines - a generalization of the standard deterministic turing machine from a uniquely determined sequence of computation steps to several possible sequences of computational steps.

A Turing Machine is a mathematical model of a computation defining an abstract machine. In this article, we learn about the different variations/types of Turing machines.

A Turing machine is a mathematical model of a computation that defines an abstract machine. In this article, we learn about Turing machines, how they are defined formally and informally, and the Church-Turing thesis.

It is much easier to work with context-free grammars if the given Context Free Grammar is in a normal form. In this article we discuss the Chomsky Normal Form.

Regular expressions are a means to describe languages, in this article, we proved that every regular expression describes a regular language and that every DFA can be converted to a regular expression that describes a language.

In this article we have discussed three languages operations namely, union, concatenation and kleen closure.

In this article, we discuss finite automata, a state machine that takes a regular expression and changes its state accordingly for each literal and when the transitions reach the final state, the string is accepted and thus it is said to be a valid token of a language.

In this article we introduce the theory of computation and lay the foundation for articles to come by going over mathematical concepts and how to prove theorems which will deem useful in understanding the domain of compiler design.

We have explain the meaning and importance of Church Turing Thesis in Theory of Computation along with its applications and limitations.

We have presented some Questions which can be solving using Pumping Lemma in Theory of Computation. You must try these questions to test your understanding of Pumping Lemma before your examination.