Language Theory And Automata

• exposé - matière potentielle : the hypothesis
• mémoire
• exposé - matière potentielle : s
• exposé
• cours - matière potentielle : overview
• expression écrite

8/31/11 1 CS240 Language Theory And Automata Fall 2011 Introduction •  You are about to embark on the study of a fascinating and important subject: the theory of computation –  Fundamental mathematical properties of computer hardware, software, and certain applications of these –  Seek to determine •  What can and cannot be computed •  How quickly something can be computed •  How much memory is needed to compute something •  Which type of computational model can be used Obvious connections with engineering practice, but also purely philosophical aspects Why study this stuff? • Theoretical computer science has many fascinating big ideas, but also many small and sometimes dull details –  The more

• strings from alphabet σ - σ
• practice with formal definitions of computation
• uncountable sets
• finite subset
• mathematical notation
• definitions
• elements
• statement
• theory
• computer