Formal Language and Automata Theory

Formal Language

• A formal language is a set of strings of symbols from a finite alphabet that can be generated by a set of rules.
• Formal languages can be classified into:
  • Recursive language: a language that can be decided by a Turing machine in a finite amount of time.
  • Recursively enumerable language: a language that can be generated by a Turing machine in a finite amount of time.

Automata Theory

• Automata theory is the study of abstract machines that can perform computations on strings of symbols.
• Types of automata:
  • Finite Automaton (FA): a simple machine that can recognize regular languages.
  • Pushdown Automaton (PDA): an extension of FA that uses a stack to recognize context-free languages.
  • Turing Machine (TM): a more powerful machine that can recognize recursively enumerable languages.

Regular Languages

• A regular language is a language that can be recognized by a finite automaton.
• Properties of regular languages:
  • Closure properties:
    • Union: the union of two regular languages is regular.
    • Intersection: the intersection of two regular languages is regular.
    • Complement: the complement of a regular language is regular.
  • Pumping lemma: a tool used to prove that a language is not regular.

Context-Free Languages

• A context-free language is a language that can be generated by a context-free grammar.
• Properties of context-free languages:
  • Closure properties:
    • Union: the union of two context-free languages is context-free.
    • Intersection with a regular language: the intersection of a context-free language and a regular language is context-free.
  • Pumping lemma for context-free languages: a tool used to prove that a language is not context-free.

Turing Machines

• A Turing machine is a mathematical model for computation that consists of:
  • Tape: an infinite tape divided into cells, each cell can hold a symbol from a finite alphabet.
  • Head: a read/write head that can move along the tape and perform operations.
• Types of Turing machines:
  • Deterministic Turing machine (DTM): a Turing machine that makes a decision based on the current state and input symbol.
  • Non-deterministic Turing machine (NTM): a Turing machine that can make multiple choices based on the current state and input symbol.

Problems and Reductions

• Decidability: a problem is decidable if there exists a Turing machine that can solve it in a finite amount of time.
• Reductions: a method used to show that a problem is undecidable by reducing it to a known undecidable problem.
• Examples of undecidable problems:
  • Halting problem: the problem of determining whether a given Turing machine will halt on a given input.
  • Post's correspondence problem: the problem of determining whether a given set of strings can be transformed into another set of strings using a set of rules.

Formal Language

• Formal language is a set of strings of symbols from a finite alphabet generated by a set of rules.
• Classification of formal languages:
  • Recursive language: can be decided by a Turing machine in finite time.
  • Recursively enumerable language: can be generated by a Turing machine in finite time.

Automata Theory

• Study of abstract machines that perform computations on strings of symbols.
• Types of automata:
  • Finite Automaton (FA): recognizes regular languages.
  • Pushdown Automaton (PDA): recognizes context-free languages using a stack.
  • Turing Machine (TM): recognizes recursively enumerable languages.

Regular Languages

• Language recognizable by a finite automaton.
• Properties of regular languages:
  • Closure properties:
    • Union: union of two regular languages is regular.
    • Intersection: intersection of two regular languages is regular.
    • Complement: complement of a regular language is regular.
  • Pumping lemma: tool to prove a language is not regular.

Context-Free Languages

• Language generated by a context-free grammar.
• Properties of context-free languages:
  • Closure properties:
    • Union: union of two context-free languages is context-free.
    • Intersection with a regular language: intersection of a context-free language and a regular language is context-free.
  • Pumping lemma for context-free languages: tool to prove a language is not context-free.

Turing Machines

• Mathematical model for computation consisting of:
  • Tape: infinite tape divided into cells holding symbols from a finite alphabet.
  • Head: read/write head that moves along the tape and performs operations.
• Types of Turing machines:
  • Deterministic Turing machine (DTM): makes decisions based on current state and input symbol.
  • Non-deterministic Turing machine (NTM): makes multiple choices based on current state and input symbol.

Problems and Reductions

• Decidability: problem is decidable if a Turing machine can solve it in finite time.
• Reductions: method to show a problem is undecidable by reducing it to a known undecidable problem.
• Examples of undecidable problems:
  • Halting problem: determining whether a given Turing machine will halt on a given input.
  • Post's correspondence problem: determining whether a given set of strings can be transformed into another set of strings using a set of rules.