formal language theory (idea)

Formal Language Theory

The study of formal languages, as its name implies, studies the form, rather than the meaning of languages. More specifically: formal language theory defines a language as a (possibly infinite) set of strings. What is then studied are the ways in which a languages may be generated (or accepted), as well as the relationships between these mechanisms (for example, whether the class of languages that can be described using regular expressions are the same as the class of languages that can be described using finite state automata).

• General Information
  • Formal Language | Formal Language Theory
  • automaton
  • grammar
  • Chomsky Hierarchy
  • Language Generators vs. Language Recognizers
• Regular Languages
  • Regular grammar
  • Regular expression | regex
    • Kleene closure (Kleene star)
    • Kleene plus
    • The expressive power of regular expressions
    • star height problem
  • Finite state automaton | Finite state machine | Finite automaton
    • Deterministic finite automaton (DFA)
    • Nondeterministic finite automaton (NFA)
    • Mealy Machine
    • Moore Machine
  • Pumping lemma for regular languages
• Context-free language
  • deterministic context-free
  • Context-free grammar
  • Ambiguous grammar
  • Pushdown automaton
  • Chomsky Normal Form
  • Backus-Naur Form
  • EBNF
  • Pumping lemma for context-free languages (3rd writeup)
• Context-sensitive language
  • Context-sensitive grammar
  • Linear bounded automaton
• recursively enumerable language
  • semi-Thue grammar
  • Turing machine
  • Universal Turing Machine
• equivalent grammar
• Computational Linguistics
• People
  • John Backus
  • Noam Chomsky
  • Stephen Cole Kleene
  • Axel Thue
  • Alan Turing
  • Alfred V. Aho