Automata Theory (Quick Summary)

Automata Theory is the study of Abstract Machines and the problems these machines can solve, which is a crucial foundation for building Compilers and Programming Languages.

1. Finite Automata (FA)

An Abstract Machine with a limited number of States and no embedded Memory (operates by changing states based on Input).

• Deterministic Finite Automaton (DFA): For each State and each Input, there is exactly one path to the next State.
• Nondeterministic Finite Automaton (NFA): Can transition to multiple next States (or none) on the same Input, including skipping States without receiving Input (Epsilon transition).
• Fact: DFA and NFA have equal computational power.

2. Regular Expressions (RegEx)

Used to describe patterns of Strings (Pattern Matching).

• Has equal capability to Finite Automata (Any problem FA can solve, RegEx can describe, known as Regular Languages).
• Applications: Text processing, finding patterns in Code, Lexical analysis in Compilers.

3. Context-Free Grammars (CFG)

A system for generating Strings using a set of Rules (Productions) to describe languages with more complex structures.

• More capable than FA (e.g., can check if open/close parentheses match completely).
• The machine equivalent to CFG is the Pushdown Automata (PDA), which is essentially an FA with a Stack Memory added.
• Applications: Building Syntax Parsers in Compilers (checking if Code is written with correct Syntax).