The Theory of Computation is a branch of computer science that studies the properties of algorithms and their computational power. It studies the power and limitations of computers, and the various models of computation that can be used to solve problems. It is an important field of study that is used in many areas of computer science, including artificial intelligence, cryptography, and data science.
Chomsky Hierarchy
The Chomsky Hierarchy is a classification of formal grammars (or languages) based on their generative power. It was proposed by Noam Chomsky in 1956 and consists of four levels: Type 0 (unrestricted), Type 1 (context-sensitive), Type 2 (context-free), and Type 3 (regular). Each type of language is more powerful than the one before it, meaning that any language that can be generated by a type 0 grammar can also be generated by a type 1, 2, or 3 grammar. This hierarchy provides a way to classify languages based on their complexity and can be used to study the properties of different types of formal languages.
Empty String
Empty String is also know as Null String it is denoted by (Epsilon) or (Lamda).
Length Of String
Number of letters in a string it is denoted by .
Reverse Of String
Writing string in reverse order, denoted by .
Power Of Alphabet
The string made from alphabet will be length equal to the power of alphabet, denoted by .
Number of words =
Power Of String
The length of string concatenated by itself with the number of power, denoted by .
Regular Expression
Regular expression is used to find pattern in string.
Kleen Star
Kleen Star, also known as Kleene Closure or the star operator, is a mathematical operation used to describe a set of strings it can also represents Null String. It is denoted by the symbol and is used to denote a set of strings that can be formed by any number of repetitions of a given string. It can be used to represent patterns in strings, such as strings that contain any number of a given character. For example, the Kleen Star of the string "ab" is .
Kleen Plus
Kleen Plus, also known as Kleene Plus or the plus operator, is a mathematical operation used to describe a set of strings it can’t represent Null String. It is denoted by the symbol and is used to denote a set of strings that can be formed by any number of repetitions of a given string. It can be used to represent patterns in strings, such as strings that contain at least one of a given character. For example, the Kleen Plus of the string "ab" is .
Lexicographic Order
Lexicographic Order is an ordering of strings based on their lexical components. It is also known as alphabetical order or dictionary order. It is a way of ordering strings based on the order of their characters, with the first character being the most important. For example, in lexicographic order, the string "abc" would come before the string "abd". Lexicographic order is commonly used to sort strings, such as in sorting a list of words alphabetically.
Formal Language
A formal language is a set of strings or words that can be generated by a set of rules. It is a mathematical model used to study the properties of languages and the various models of computation that can be used to solve problems. Formal languages are used in many areas of computer science, including artificial intelligence, cryptography, and data science. A formal language consists of a set of symbols and a set of rules that govern how those symbols can be combined to form strings. Formal languages can be classified into different types, such as regular languages, context-free languages, and context-sensitive languages.
Informal Language
An informal language is a type of language that is not constrained by any set of rules or conventions. It is often used in everyday conversations, and is characterised by its use of colloquialisms, slang, and other non-standard forms of expression. Informal language is often used to express feelings and emotions, or to convey a certain tone or atmosphere. It is an important part of communication, as it helps to create a sense of intimacy and connection between people.
Finite State Machine
A Finite State Machine is a mathematical model of computation used to design computer programs and digital logic circuits. It consists of a set of states, transitions between those states, and actions that occur when transitioning between states.
Finite Automata
Finite Automata is a type of mathematical model used to represent and process data. It consists of a set of states, transitions, and input/output rules. The states represent the different stages of the process, the transitions define how the system moves from one state to another, and the input/output rules define what happens when the system receives input or produces output.
Finite Automata with output
Finite Automata with output is a type of mathematical model used to describe the behaviour of a system. It consists of a set of states, transitions between those states, and an output associated with each transition. The output can be used to determine the behaviour of the system.
Moore Machine
A Moore machine is a type of finite-state machine, which is a model of computation used to design computer programs. It consists of a set of states, inputs, and outputs, and a set of transitions between states that are triggered by inputs. The output of a Moore machine is determined solely by its current state.
Symbol | Meaning |
Q | Set of finite number of states |
Σ | Set of alphabet |
δ | Transition Function. Transition of state / Movements |
q0 | Starting state / Initial State |
▲ | Output symbol |
λ | Lambda symbol |
Mealy Machine
A Mealy machine is a type of finite-state machine which produces an output based on its current state and the input it receives.
Finite Automata without output
Finite Automata without output is a type of mathematical system that can be used to recognize patterns in data. It consists of a set of states, a set of inputs, and a set of transitions between the states. The system can be used to determine if a given input is accepted or rejected by the system.
Deterministic Finite Automata
A Deterministic Finite Automata (DFA) is a type of mathematical model used to recognize patterns in data. It is a finite state machine that takes a string of symbols as input and produces a single output. The output is determined by the current state of the machine and the input symbols.
Symbol | Meaning |
Q | Set of finite number of states |
Σ | Set of alphabet |
δ | Transition Function. Transition of state / Movements |
q0 | Starting state / Initial State |
F | Set of finite Final/Accepting states |
Non Deterministic Finite Automata
Non Deterministic Finite Automata is a type of machine that can be used to recognise patterns in a given set of data. It works by looking at the data and making decisions based on what it finds. The decisions it makes are based on a set of rules that are predetermined.
Grammar
Grammar is a finite set of formal rules that generate sentences in TOC with it’s set of rules.
It is defined as four tuples: where G is a grammar that consists of a set of production rules used to generate strings of a language.
CFL
Context Free Grammar
Context-Free Grammar (CFL) is a type of formal grammar used to describe a set of strings or words. It consists of a finite set of non-terminal symbols, a finite set of terminal symbols, and a set of rules that describe how to generate strings from these symbols. CFLs are used to describe the syntax and structure of a language, such as the syntax of a programming language or the structure of a natural language. CFLs are also used in the design of computer programs, natural language processing, and other areas of computer science.
Pushdown Automata (PDA)
A pushdown automaton is a type of automaton that employs a stack. It is a finite automaton with extra memory called stack which helps it to recognize Context Free Languages. A pushdown automaton reads a given input string from left to right. In each step, it chooses a transition by indexing a table by input symbol, current state, and the symbol at the top of the stack. A pushdown automaton can also manipulate the stack, as part of performing a transition.
Symbol | Meaning |
Q | Finite number of states |
Σ | Input alphabet |
Γ | Finite stack alphabet |
δ | Transition Function. Transition of state / Movements |
q0 | Starting state / Initial State |
z0 | Starting stack symbol |
F | Set of finite Final/Accepting states |
Turning Machine
A Turing Machine is a mathematical model which consists of an infinite length tape divided into cells, on which input is given. It consists of a head which reads the input tape. A state register stores the state of the Turing machine. After reading an input symbol, it is replaced with another symbol, its internal state is changed, and it moves from one cell to the right or left. If the TM reaches the final state, the input string is accepted, otherwise rejected.
Symbol | Meaning |
Q | Finite number of states |
Σ | Input alphabet |
Γ | Tape Symbol |
δ | Transition Function |
q0 | Initial State |
B | Blank Symbol |
F | Set of Final States |
Decidability
A language is Decidable or Recursive if a Turing machine can be constructed which accepts the strings which are part of language and rejects others.
Undecidable
A problem is undecidable if we can’t construct an algorithms and Turing machine which can give yes or no answer.