Post

Theoretical foundations of computer sciences

Posted
By Yevhenii Deshchenko
1 min read
Theoretical foundations of computer sciences

Chomsky Hierarchy of Formal Languages

Type 0 - Recursively Enumerable Languages
Automaton: Turing Machine
Rules: No restrictions on grammar (can be any computational process).
Example: Any computable function, including complex languages like natural languages.

Type 1 - Context-Sensitive Languages
Automaton: Linear Bounded Automaton (LBA) (Turing Machine with limited tape)

Type 2 - Context-Free Languages (CFL)
Automaton: Pushdown Automaton (PDA)

Type 3 - Regular Languages
Automaton: Finite Automaton (FA) / Regular Expressions
Example: Binary strings with an even number of 0s, identifiers in programming languages

Context-Free Grammar (CFG)

A context-free grammar (CFG) is a way to describe context-free languages (CFLs), which are exactly the languages recognized by Nondeterministic Pushdown Automata (NPDAs).

A grammar is a 4-tuple: \(G = (N, T, P, S),\) where:

  • N - non-terminal symbols (variables)
  • T - terminal symbols (actual symbols in the language)
  • P - production rules ($A \implies \alpha$, where $A$ is a non-terminal and $alpha$ is a string of terminals and/or non-terminals)
  • S - start symbol (the derivation begins here)

Pushdown Automaton (PDA)

A Pushdown Automaton (PDA) is a finite state machine with a stack for additional memory. There are two types:

  • Deterministic Pushdown Automaton (DPDA)
  • Nondeterministic Pushdown Automaton (NPDA)

PDA is defined as a 7-tuple:
\(M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F),\) where:

  • $Q$ - Set of states
  • $\Sigma$ - Input alphabet
  • $\Gamma$ - Stack alphabet
  • $\delta$ - Transition function
  • $q_0$ - Start state
  • $Z_0$ - Initial stack symbol
  • $F$ - Set of accepting states

Transition function $\delta(q, a, X) = (q’, \gamma)$, where:

  • $q$ is current state
  • $a$ is whats left of input
  • $X$ is a stack

Deterministic Pushdown Automaton (DPDA):

  • $\delta(q, a, X)$ has at most one possible transition

Nondeterministic Pushdown Automaton (NPDA):

  • $\delta(q, a, X) = {(q_1, \gamma_1), (q_2, \gamma_2), \dots}$
  • Can have multiple possible transitions and $\epsilon$-moves
learning
This post is licensed under CC BY 4.0 by the author.