Introduction Wen-Guey Tzeng Computer Science Department National Chiao Tung University Formal languages and finite automata • We have been building computing machines for solving computing problems • Questions – – – – What is a computing machine? How do we study it? What can it do? What is a problem to be solved by a computing machine? • Finite automata: abstract models of computing machines • Formal languages: formal representation of computing problems 2 Classification • Finite automata: by types of memories – Finite automata – Pushdown automata – Turing machines • Formal languages: by types of grammars – – – – – Regular languages Context-free languages Recursive languages (solvable) Recursively enumerable languages (semi-solvable) … 3 Relations between languages and automata • Finite automata and regular languages • Pushdown down automata and context-free languages • Turing machines and recursive languages • Complexity classes: by runtime or space used by Turing machines – – – – P: polynomial time computable NP: non-deterministic polynomial time computable EXP: solvable in exponential time … 4 Computing machines Formalization Abstraction Yes/No problems Computing problems Formal languages Classifications: grammars, machines, etc. Relations • • • • • Finite automata Classifications: memory, runtime, space, etc. Regular vs. finite automata Context-free vs. pushdown Recursive vs. Turing machines Complexity classes … 5 Applications • • • • • • • Programming languages Compilers Natural language processing Algorithm design Software engineering Pattern recognitions … 6 7 • How to compile a Java program, like the above? • We need a grammar for the Java programming language • Context-free grammar 8 9 Mathematical notation • Set: a collection of elements – |S| – SxT={(x, y) | xS, yT} • Function – f: S1S2 • Binary relation – R S1xS2 – xS1 and yS2 has relation R if (x, y)R 10 • Graph: G=(V, E) – V: node set – EVxV: edge set • Tree – Level – Height 11 Proof Techniques • Proof by induction – For some k, we know (prove) that P1, P2, …, Pk are true – The problem is that for nk, the truths of P1, P2,…, Pn imply the truth of Pn+1 • Example – Theorem: a binary tree of height n has at most 2n leaves 12 • Proof by contradiction – To show that P is true. – We assume that if P is false, then … • Example: – Theorem: sqrt(2) is not rational. 13 Three Basic Concepts • Languages (yes-no problems) – Symbol set (alphabet) ={a, b, c, …} – String: w=a1a2…an, n0, ai – |w|: length of string – String concatenation: w1w2 – String reversing: wR=anan-1…a1 – Prefix(w)={, a1, a1a2, …, a1a2…an} – Suffix(w)={, an, an-1an, …, a1a2…an} 14 – Empty string • • ||=0 • w= w=w – *: the set of all strings over • * over {a,b} = {, a, b, aa, ab, ba, bb, …} – + = * - {}: set of all non-empty strings – A language L over is a subset of *: a set of strings 15 – LR = {wR: wL } – L c = * - L – L1L2 = {xy: xL1, yL2} – Ln = {x1x2…xn: xiL} • L0 = {} • L* = L0 L1 … • L+ = L1 L2 … 16 • Grammar: a set of rules for generating strings – G=(V, T, P, S) – V: set of variables – T: set of terminals (symbols) – P: set of production rules – SV: the start variable 17 Example G=({S,A,B}, {a,b}, {SaA, AbS, S}, S) • String generation/derivation • The language generated by G – L(G) = {w | S * w} 18 • Problem: find grammars for languages over ={a, b} – L={anbn | n0} – L={w | na(w)=nb(w)} – L={anbm | nm0} 19 • Automaton: an abstract model of a digital computer – Input – Control unit: represented by “states” – Storage – Output – Operating in discrete time frame 20 21

© Copyright 2021