automata-seminar

This contains the latex code and generated pdf for the seminar on UMC205 Automata Theory, Semester 4.

Büchi Automata

A Büchi automaton is a type of $w$-automaton, which is a formalism for accepting infinite sequences of input. Büchi automata are used in formal language theory, the theory of computation, and formal verification. They are named after the mathematician Julius Richard Büchi, who introduced them in 1960.

Topics Covered

• Introduction
• Definition
• Acceptance
• Deterministic Büchi Automata
• Complementation
• Emptiness Problem
• Closure Properties
• Relationship with Regular Languages
• Relationship with $\omega$-Regular Languages
• Relationship with $\mu$-Calculus And other miscellaneous topics.