Computability and formal languages 1982/83.

For 4th year mathematics students. Official name: Algebra superiore.

DIFFERENCE EQUATIONS Product of polynomials and formal power series Polynomial division Division in the ring of formal power series Partial fraction decomposition Generating function of a sequence and some applications Generalities on difference equations Linear difference equations with constant coefficients COMPUTABLE FUNCTIONS Categories Partial functions Primitive recursion Ackermann's function Church's thesis Elementary functions Recursive functions Iterations Register machines FORMAL LANGUAGES Recursive and enumerably recursive languages Chomsky grammars Finite state automata Non deterministic automata Regular grammars Decidibility Context-free grammars Push-down automata Semigroups and formal languages M-systems