Formal Languages and Logic/Finite state automata

deterministic finite state automaton A deterministic finite state automaton (DFA for short) is a quintuple , where is a finite set, is a finite alphabet, is a function, , and . state Let be a deterministic finite state automaton. Then a state of is an element of . initial state Let be a deterministic finite state automaton. Then the initial state of is . transition function Let be a deterministic finite state automaton. Then is the transition function. accepting state Let be a deterministic finite state automaton. Then an accepting state is an element of . every accepting state is a state Let be a deterministic finite state automaton. Then every accepting state of is a state. This is because . generalized transition function Let be a deterministic finite state automaton. Then the generalized transition function is the function defined on by induction on word length as thus: for a singleton word , whenever , then language accepted by a deterministic finite state automaton Let be a finite state automaton. The language accepted by the deterministic finite state automaton by is defined to be . finite state automata accept precisely regular languages Whenever is a finite state automaton, the language accepted by is regular. Whenever is a regular language, there exists a finite state automaton that accepts it. Let first be a finite state automaton. Define a Chomsky grammar as follows: , and the productions shall be given by