Catégorie : Theoretical Computer Science

  Introduction to Automata Theory Automata theory : the study of abstract computing devices, or ”machines” Before computers (1930), A. Turing studied an abstract machine (Turing machine) that had all the capabilities of today’ s computers (concerning what they could compute). His goal was to describe precisely the boundary between whata computing machine could do…

Contents 1 Mathematical Preliminaries 3 2 Formal Languages 4 2.1 Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Languages . . . . . . . . . .…

Outline 1-Introduction Linguistics and formal languages Computer science and formal languages Generative vs. recognition 2-Formal languages 3-Grammars Chomsky hierarchy 4-Finite-state automata Deterministic  nite-state automata Extensions of DFA FA and linear grammars 5-Regular expressions 6-Context-free languages and pushdown automata 7-References Source : http://www.sti.uniurb.it/aldini/publications/lfga.pdf

  Course Titles ----- Authors Formal Languages, Grammars, and Automa  Alessandro Aldini Formal Languages and Automata Theory GD. Goswami and K. V. Krishna  Automata Theory and Languages   Mirian