Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last updated: Jun 17, 2022

Theory of Computation

Theory of Computation(TOC) is a theoretical branch of Computer Science and Mathematics which mainly deals with the logic of computation with respect to simple machines, referred to as automata. In the beginning, it may appear a little confusing but once you understand the concepts, you’ll find it to be interesting. So let’s explore together!

Basics of TOC

In this blog series, we’ll learn about different basic concepts of Theory of Computation such as Deterministic Finite Automata (DFA), Non-Deterministic Finite Automata (NFA), Myhill Nerode Theorem, Conversions, Finite State Machine, and much more.
Introduction to Automata MEDIUM
In this article, we will explore the world of Automata, how automata perform tasks in a wide range of devices and machines available worldwide.
Introduction of Automata Theory
This article will cover the introduction of automata theory.
Author Riya
3 upvotes
Finite State Machine
This article will discuss the Finite State Machine along with Deterministic and Non Deterministic finite automata in detail.
Deterministic Finite Automata or DFA
In this blog, we will discuss Finite Automata, its formal definition, its types, Deterministic Finite Automata, its formal definition, needs, and examples
Non-Deterministic Finite Automata EASY
In this blog, we will go through Non-Deterministic Finite Automata, its need, in which condition any string is accepted by an NFA, and the major differences between NFA and DFA.
Conversion from NFA to DFA MEDIUM
This article will discuss a lot about the conversion of NFA to DFA, that is Nondeterministic Finite Automata(NFA) to Deterministic Finite Automata(DFA).
Conversion of Epsilon - NFA to NFA MEDIUM
This article will discuss the method of conversion of epsilon - NFA to NFA
Author Riya
2 upvotes
DFA Minimization MEDIUM
In this article, we will study how to convert a DFA into an equivalent DFA having the minimum number of states.

Regular Expression

The language accepted by finite automata can be easily described by simple expressions called Regular Expressions. It is the most effective way to represent any language. Regular Expression can also be described as a sequence of patterns that defines a string. Regular expressions are used to match character combinations in strings.
Regular Expression
In this blog, we will learn about Regular Expressions as well as some properties and examples related to it.
Examples of Regular Expression
In this article, we see some examples of converting a language of strings into regular expressions.
Conversion Of Regular Expressions to Finite Automata EASY
Converting a regular expression to a finite automaton means turning a pattern description into a step-by-step machine that checks if a string fits that pattern.
Arden's Theorem MEDIUM
Unlock the power of Arden's Theorem in automata theory and formal languages! Explore how this fundamental concept simplifies the solution of linear equations in regular languages.
NFA to Regular Expression
In this article, we will learn how to convert a given NFA to a regular expression using Arden’s Theorem.
DFA to Regular Expression Conversion EASY
In the following article, we discuss an important topic in the Theory of Computation which is DFA to Regular Expression Conversion with the help of an example
What is Pumping Lemma? HARD
The word pumping refers to generating many input strings by pushing a symbol in an input string repeatedly. The word Lemma refers to the intermediate theorem in a proof.

CFG

CFG stands for context-free grammar. It is a formal grammar that is used to generate all possible patterns of strings in a given formal language. Let’s explore CFG in order to understand it better.
Derivation Tree
In this blog, we will learn about what is derivation tree, its syntax, its representation, its properties, its types, and much more.
Ambiguous Grammar
This article will cover the topic of ambiguous grammar along with some examples.
Unambiguous Grammar
In this article, we will learn about Unambiguous Grammar and the rules to convert Ambiguous Grammar into Unambiguous Grammar.
Difference between Ambiguous and Unambiguous Grammar
This blog covers the concept of ambiguous and unambiguous grammar and the differences between them.
Simplification of CFG(Context-Free Grammars) MEDIUM
Let's understand the simplification of CFG & Learn how to simplify context-free grammars by removing useless symbols, epsilon productions, and unit productions.
Chomsky Normal Forms(CNF) EASY
In this article, we will learn the Chomsky Normal Forms, and how to convert CFG to CNF.
Greibach Normal Form (GNF) MEDIUM
GNF stands for Greibach Normal Form. In this article, we will learn about the Greibach Normal Form of Grammar and the steps to convert the normal form of Grammar into GNF.
Pumping Lemma for Context Free Language(CFL) MEDIUM
This article will cover the topic of Pumping Lemma for context-free language and its theorem.