FORMAL LANGUAGES - TUT

← Back to document page

FORMAL LANGUAGESKeijo Ruohonen2009Contents1I WORDS AND and REGULAR Expressions and of Words. Finite s of Machines and Transducers (A Brief Overview)18III s Hierarchy25IV of Algorithms (A Brief Overview) and Complements of Problems. Post s Correspondence Problem42V of CS-Languages51VI Complexity Classes (A Brief Overview)56VII Sch utzenberger s Sardinas Patterson Sums. Prefix Codes and Huffman s Algorithmiii68VIII LINDENMAYER S L-Systems or L-Systems with Interaction73IX FORMAL POWER as a FORMAL Power General FORMAL Power FORMAL Power Series. Sch utzenberger s Representation and Hadamard s of FORMAL Power Languages90References92IndexForewordThes e lecture notes were translated from the Finnish lecture notes for the TUT course Formaalit kielet . The notes form the base text for the course MAT-41186 FormalLanguages . They contain an introduction to the basic concepts and constructs, as seenfrom the point of view of LANGUAGES and grammars.

In formal language theory defining languages and investigating languages via their definitions is paramount. Thus only a (minuscule) portion of all possible languages enters

  Language, Formal, Formal language, In formal language