TOC Notes
TOC Notes

TOC Notes

Tags
TOC
Published
March 16, 2023
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

notion image
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.