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.

1 upvote

Introduction of Automata Theory

This article will cover the introduction of automata theory.

3 upvotes

Finite State Machine

This article will discuss the Finite State Machine along with Deterministic and Non Deterministic finite automata in detail.

Author apoorv007

2 upvotes

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

Author Shivani Singh

0 upvotes

Non-Deterministic Finite Automata EASY

Non-Deterministic Finite Automata | NFA: This article covers the graphical representation of NFA, need, acceptance, and DFA vs NDFA.

Author Shivani Singh

1 upvote

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

Author apoorv007

1 upvote

Conversion of Epsilon - NFA to NFA MEDIUM

This article will discuss the method of conversion of epsilon - NFA to NFA

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.

Author Sanjana kumari

2 upvotes

Moore & Mealy Machine

Moore Machines are finite state machines with output value and their output depends only on the present state. Whereas Mealy Machines are also finite state machines with output value and its output depends on the present state and current input symbol.

Difference between Mealy Machine and Moore Machine MEDIUM

This article covers the difference between Mealy and Moore machines with examples, and outlines their features and the conversion process between them.

Author Jaglike Makkar

0 upvotes

Difference Between Mealy and Moore Machine MEDIUM

Mealy machines and Moore machines are types of finite state machines used in digital systems. Learn the difference between Mealy and Moore machines and how these types of finite state machines differ in their output timing and design.

Author Muskan Gupta

5 upvotes

Conversion of Moore To Mealy Machine

This article will discuss a lot about the Conversion of Moore To Mealy Machine with illustrated examples for better understandability.

Author apoorv007

1 upvote

Conversion of Mealy Machine to Moore Machine MEDIUM

Moore and Mealy Machines are types of transducers used in computer science. They generate outputs based on the input and the current state (Mealy Machines) or just the current state (Moore Machines).

Author brainstorming

1 upvote

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.

Examples of Regular Expression

In this article, we see some examples of converting a language of strings into regular expressions.

Author Anant Dhakad

0 upvotes

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.

1 upvote

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.

Author Juhi Sinha

1 upvote

NFA to Regular Expression

In this article, we will learn how to convert a given NFA to a regular expression using Arden’s Theorem.

Author Jaglike Makkar

0 upvotes

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

Author Anant Dhakad

0 upvotes

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.

3 upvotes

Regular Grammar

In this blog series, we will introduce Context-Free Grammars or CFG. A context-free grammar (CFG) is a formal grammar that is used to generate all the possible patterns of strings. We’ll learn about Chomsky Normal Forms(CNF), Greibach Normal Forms(GNF), and Pumping Lemma(CFL).

Regular Grammar

In this blog, we will learn about Regular Grammar, and its type, and will be discussing its various functionalities.

0 upvotes

Context-Free Grammar and Language

This blog will learn about Context-Free Language and Context-Free Grammar, its tuples with explanations and examples. And we will learn about the properties, applications, and types of grammar.

Author Naman Kukreja

1 upvote

Regular Expression And Finite Automata MEDIUM

In this blog, we will learn about Regular Expression and Finite Automata with the help of relevant examples.

0 upvotes

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.

Author Naman Kukreja

0 upvotes

Ambiguous Grammar

This article will cover the topic of ambiguous grammar along with some examples.

Author Soumya Agrawal

0 upvotes

Difference between Ambiguous and Unambiguous Grammar

This blog covers the concept of ambiguous and unambiguous grammar and the differences between them.

Author Muskan Gupta

4 upvotes

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.

Author GAZAL ARORA

2 upvotes

Chomsky Normal Forms(CNF) EASY

In this article, we will learn the Chomsky Normal Forms, and how to convert CFG to CNF.

Author brainstorming

1 upvote

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.

Author GAZAL ARORA

1 upvote

Pumping Lemma for Context Free Language(CFL) MEDIUM

This article will cover the topic of Pumping Lemma for context-free language and its theorem.

Author Soumya Agrawal

0 upvotes

Pushdown Automata

Pushdown Automata is a finite automaton with extra memory called stack which helps Pushdown automata to recognize Context-Free Languages. The word pushdown stands for that the stack can be pushed down as operations can only work on the elements which are on the top of the stack.

Pushdown Automata(PDA) EASY

Discover the fundamentals of pushdown automata in our comprehensive article, exploring its role in computer science and its applications in parsing and language recognition.

Author vishal teotia

1 upvote

Introduction to Pushdown Automata

The article will cover the topic of PushDown automata and the language accepted by them.

Author Soumya Agrawal

1 upvote

Non-deterministic Pushdown Automata

In this article, we will learn about Non-Deterministic Pushdown Automata and the formal definitions of NDPAs.

Author Anant Dhakad

0 upvotes

CFG to PDA Conversion EASY

In this article, we will be learning an approach for converting Context-Free Grammar to Pushdown Automata. Also will see an example of converting CFG to PDA.

Author soham Medewar

1 upvote

Turing Machine

Turing machine was invented in 1936 by Alan Turing. It is a computational model, like Finite Automata (FA), Pushdown automata (PDA), which works on unrestricted grammar. The Turing machine is the most powerful computation model when compared with FA and PDA.

Automata Turing Machine

This article will cover the topic of the Turing Machine and its formal definition with some examples.

Author Soumya Agrawal

1 upvote

Turing Machine in TOC HARD

Turing Machine in TOC is a hypothetical computing machine that can read, write, and erase symbols on a tape-based on a set of rules.

Author GAZAL ARORA

1 upvote

Multitape Turing Machine EASY

Multi-tape Turing Machines have many tapes, each with its own head. Each of the heads can move independently of the others.

Author Anant Dhakad

0 upvotes

Non-Deterministic Turing Machine

In this article, we will learn about Non-deterministic Turing machines and its definition.

Author Anant Dhakad

0 upvotes

Chomsky Hierarchy in Theory of Computation(TOC) EASY

The Chomsky hierarchy is a system for classifying formal grammars and languages in computer science and linguistics.

Author Sanjana kumari

2 upvotes

Undecidability

In theory of computation, a problem that cannot be decided by algorithmic means even after giving an unlimited resource and an infinite amount of time is termed as undecidable. We’ll explore more topics like Decidability and Undecidability, Universal Turing Machine, Halting, and Post Correspondence Problem.

Universal Turing Machine MEDIUM

A Turing machine is called a Universal Turing Machine if it is powerful enough to simulate any other Turing Machine. In this article, we will learn about Universal Turing Machines.

Author GAZAL ARORA

2 upvotes

Halting Problem in Theory of Computation MEDIUM

The Halting Problem in Theory of Computation is determining whether a computer program will eventually stop or run forever.

Author GAZAL ARORA

1 upvote

Decidability and Undecidability Problems MEDIUM

In this article, we will discuss Decidability and Undecidability language. We will also discuss the recursive language.

Author Anant Dhakad

0 upvotes

Post Correspondence Problem MEDIUM

The Post Correspondence Problem (PCP) is a classic decision problem in theoretical computer science and mathematical logic, formulated by Emil Post in 1946.

Author yuvatimankar

1 upvote