Introduction to Theory of Computation

A field that develops formal mathematical models of computation, reflecting real-world computers.

Deals with "computation models", like Finite Automata, Context-Free Grammars, and Turing Machines, and their properties.

A computation model used in text processing, compilers, and hardware design.

Used to define programming languages and in Artificial Intelligence.

A simple abstract model of a "real" computer.

Studies solvable and unsolvable mathematical problems by defining computers, algorithms, and computation.

Fundamental mathematical problems that cannot be solved by a computer.

Focuses on computational difficulty, classifying problems as easy or hard to solve.

Efficiently solvable.

A crucial step in mathematical induction, it assumes a statement is true for a certain value (like 'm') to prove it's true for the next value.

If you have more items than containers, at least one container must hold more than one item.

A method to prove that a set is uncountable by constructing a new element not already in the set.

A relationship between items in a set. (like, 'is greater than', or 'is related to').

A function where each input gives a unique output.

A set with a specific, limited number of elements.

A set containing all elements from either set A or set B (or both).

A set containing only the elements common to both set A and set B.

A set containing elements in A but not in B.

All elements not in set A.

Sets with no common elements (intersection is empty).

The number of elements in set A.

Set of all possible subsets of set A.

Set of all ordered pairs (x, y) where x is in A and y is in B.

A set of ordered pairs (s, t) where s is in S and t is in T.

Set of all first elements in a relation.

Set of all second elements in a relation.

A set of strings over an alphabet. Any subset of all possible strings.

A finite set of symbols used to form strings. Example: {0, 1}.

Combining two languages into one by joining strings from each.

All possible strings formed by concatenating zero or more strings from a given language L

A formal way to describe sets of strings that form a regular language.

A language that can be described by a regular expression.

Adding or removing closing operations within a parenthesis or bracket structure doesn't alter the language/expression. Changes are syntactically valid but semantically identical to the original.

Represents the empty language, raised to the power of √ ,meaning any combination of the empty language which is still the empty language (e).

Represents the empty string, raised to the power of √ (or any number), which remains the empty string (e).

Defines a language (L) containing one or more instances of strings from the original language L, represented as L+ It also denotes the replication of this language by concatenation of L and zero or more copies. The order doesn't matter.

Represents the set of all strings formed by concatenating zero or more strings from the original language L, indicating all possible combinations including the empty string (e).

Represents the language containing either the empty string (e) or a single string from the original language L. Indicates either the empty or an original language instance.

Verifying the equivalence of regular expressions by converting them to deterministic finite automata (DFA) and minimizing them, and also testing if the law holds under concrete symbols (like substituting values for variables and examining if each side produces the same result for various combinations).

A way to test a law/equality of regular expressions. By testing the law/equality with substitutions of any values (especially for the language).

Kleene closure, including the empty string and all possible concatenations of strings in the language L.

Positive closure, including all possible concatenations of strings in the language L, excluding the empty string.

A language that can be created from the union, concatenation, and Kleene star operations.

A formal notation to describe a regular language.

Combines elements from multiple sets.

Joining two strings end-to-end.

Allows zero or more repetitions of a string.

L + M = M + L

(L + M) + N = L + (M + N)

(LM)N=L(MN)

L + Ø = Ø + L = L

L.e = e.L = L

ØL = LØ = Ø

L(M+N)=LM+LN

(M+N)L=ML+NL

L+L=L

L*