Exploring Chomsky Hierarchy

CPTR 437 Final Project by Edward Breja

Jump In!

Regular Language

A language is called a regular language if some finite automaton recognizes it

Finite automaton

A finite automaton (FA) is a simple idealized machine used to recognize patterns within input taken from some character set (or alphabet). The job of an FA is to accept or reject an input depending on whether the pattern defined by the FA occurs in the input.

Formally, a finite automaton is a 5-tuple (Q, Σ, δ, q₀, F ) where
1. Q is a finite set called the states
2. Σ is a finite set called the alphabet
3. δ : Q × Σ → Q is the transition function
4. q₀ ∈ Q is the start state
5. F ⊆ Q is the set of accept states
Regular grammar

The purpose of a (regular) grammar is to specify how to form grammatically correct strings in the language the grammar represents.

Formally, a regular grammar is a mathematical object, G, with four components, G = (N, Σ, P, S), where
1. N is a nonempty, finite set of nonterminal symbols
2. Σ is a finite set of terminal or alphabet symbols
3. P is a set of grammar rules (eg. A → aB for [A,B] ∈ N, a ∈ Σ)
4. S ∈ N is the start symbol

Deterministic Context Free Language

Deterministic context-free languages (DCFLs) are a proper subset of context-free languages

Deterministic pushdown automaton

Formally, a deterministic pushdown automaton is a 6-tuple (Q, Σ, Γ, δ, q₀, F ), where Q, Σ, Γ, and F are all finite sets, and
1. Q is the set of states
2. Σ is the input alphabet
3. Γ is the stack alphabet
4. δ : Q × Σε × Γε → (Q × Γε) ∪ {∅} is the transition function
5. q₀ ∈ Q is the start state
6. F ⊆ Q is the set of accept states
Deterministic context-free grammar

A deterministic context-free grammar is a context-free grammar such that every valid string has a forced handle. For any CFG we construct an associated DFA DK that can identify handles. DK accepts its input z if
1. z is the prefix of some valid string v = zy, and
2. z ends with a handle of v.

Context Free Language

A context-free language is any language that is generated by a context-free grammar

Pushdown automaton

A pushdown automaton (PDA) is a type of automaton that employs a stack.

Formally, a pushdown automaton is a 6-tuple (Q, Σ, Γ, δ, q₀, F ), where Q, Σ, Γ, and F are all finite sets, and
1. Q is the set of states
2. Σ is the input alphabet
3. Γ is the stack alphabet
4. δ : Q × Σε × Γε → P(Q × Γε) is the transition function
5. q₀ ∈ Q is the start state
6. F ⊆ Q is the set of accept states
Context-free grammar

A context-free grammar (CFG) is defined as a grammar in which every production rule is of the form 𝐴→𝛼, where 𝐴 is a variable and 𝛼 is a sequence of variables and terminals.

Formally, a context-free grammar is a 4-tuple (V, Σ, R, S), where
1. V is a finite set called the variables
2. Σ is a finite set, disjoint from V, called the terminals
3. R is a finite set of rules, with each rule being a variable and a string of variables and terminals
4. S ∈ V is the start variable

Context Sensitive Language

A context-sensitive language is a language that can be defined by a context-sensitive grammar

Linear bounded automaton

A linear bounded automaton (LBA) is a restricted form of Turing machine. It is described as a multi-track non-deterministic Turing machine with a tape of some bounded finite length. The computation is restricted to the constant bounded area. The input alphabet contains two special symbols which serve as left end markers and right end markers which mean the transitions neither move to the left of the left end marker nor to the right of the right end marker of the tape.
Context-sensitive grammar

A Context-sensitive grammar is an unrestricted grammar in which all the productions are of form α → β where α and β are strings of non-terminals and terminals.

Formally, context-sensitive grammar has 4-tuples, G = (N, Σ, P, S), where
1. N is a set of non-terminal symbols
2. Σ is a set of terminal symbols
3. P is the finite set of productions
4. S is the start symbol of the production

Recursive Language

A language is recursive if there exists a Turing machine that accepts every string in the language and rejects everything else

Turing machine

A turing machine for a recursive language can't go into an infinite loop. It has to clearly reject or accept any string input.

Formally, Turing machine is a 7-tuple, (Q, Σ, Γ, δ, q₀, q_accept q_reject), where Q, Σ, Γ are all finite sets and
1. Q is the set of states
2. Σ is the input alphabet not containing the blank symbol ␣
3. Γ is the tape alphabet, where ␣ ∈ Γ and Σ ⊆ Γ
4. δ: Q × Γ → Q × Γ × {L,R} is the transition function
5. q₀ is the accept state
6. q_accept ∈ Q is the accept state
7. q_reject ∈ Q is the reject state
Unrestricted grammar

In unrestricted grammars, productions have form u → v where u and v are any strings of terminals and/or variables

Recursive Enumerable Language

A language is recursively enumerable if there is a Turing machine that accepts every string in the language and doesn't accept everything else

Turing machine

A turing machine for a recursive enumerable language can go into an infinite loop. Strings that are not in the language may be rejected or may cause the Turing machine to go into an infinite loop.

Formally, Turing machine is a 7-tuple, (Q, Σ, Γ, δ, q₀, q_accept q_reject), where Q, Σ, Γ are all finite sets and
1. Q is the set of states
2. Σ is the input alphabet not containing the blank symbol ␣
3. Γ is the tape alphabet, where ␣ ∈ Γ and Σ ⊆ Γ
4. δ: Q × Γ → Q × Γ × {L,R} is the transition function
5. q₀ is the accept state
6. q_accept ∈ Q is the accept state
7. q_reject ∈ Q is the reject state
Unrestricted grammar

In unrestricted grammars, productions have form u → v where u and v are any strings of terminals and/or variables