Terminology related to TOC 1. Alphabet (Σ) It is a finite, non-empty set of symbols. For example: Σ = {a, b} 2. String It is a finite sequence of symbols from an alphabet. For example: abba 3. Language (L) It is a set of strings over an alphabet. For example: Read more…
Difference between TOC in DFA and NFA Slno Similarities 1. Both are transition functions of automata. 2. Both have same power. 3. Slno DFA NFA/NDFA 1. Stands for “Deterministic Finite Automata”. Stands for “Non-deterministic Finite Automata”. 2. No empty string transitions occurs in DFA. Empty string transitions may also possible. Read more…
Introduction The concept of Chomsky Classification was developed by linguist Noam Chomsky in 1956. The Chomsky Classification is also known as the Chomsky hierarchy. Definition The Chomsky Classification is a hierarchy that categorizes grammars and languages into four types based on their generative power and computational models. The Chomsky hierarchy is a classification of Read more…
Introduction The Turing Machine (TM) was proposed by Alan Turing (1936). Definition A Turing Machine is an abstract machine or theoretical computational model that manipulates symbols on an infinite tape according to a set of rules. A Turing Machine is defined in a 7-tuple form: M=(Q,Σ,Γ,δ,q0,B,F) where, Q = Finite set of Read more…
Introduction A Context-Free Grammar (CFG) is a formal system that provides a precise way to define valid strings in a language. Definition A Context-Free Grammar (CFG) is a formal grammar used to define context-free languages, where each production rule has a single non-terminal on the left-hand side. A language is Read more…
Introduction The Pumping Lemma states that every regular language has a pumping length such that sufficiently long strings can be decomposed and repeated while remaining in the language. Definition The Pumping Lemma is a powerful theoretical tool that helps identify the limitations of finite automata and distinguish regular languages from Read more…
Introduction A language is regular if and only if it can be accepted by a finite automaton. Finite Automata (FA) is the simplest computational model/abstract machine in the Theory of Computation (TOC). Finite Automata form TOC’s base, and are extended by Pushdown Automata (for context-free languages) and Turing Machines. Definition Read more…
Regular Language(RL) A regular language is any set of strings over a finite alphabet (Σ) that can be accepted or recognized by a finite automaton (DFA or NFA). Regular languages are the simplest class of languages in the Chomsky hierarchy of formal languages, a concept within the Theory of Computation Read more…
History The concept and roots of TOC originated in the 1930s/early 20th century during the “Crisis in Foundations of Mathematics,” when pioneering logicians like Kurt Gödel, Alonzo Church, and Alan Turing independently tackled Hilbert’s Entscheidungsproblem (decision problem). Modern TOC started in the 1970s. Introduction The Theory of Computation or Theory Read more…