TAILIEUCHUNG - Lecture Theory of automata - Lecture 45
This chapter presents the following content: Turing machine, examples, DELETE subprogram, example, INSERT subprogram, example, whether the given string is generated by the given CFG (membership), example, parsing techniques, top down parsing, example. | Recap lecture 44 Decidability, whether a CFG generates certain string (emptiness), examples, whether a nonterminal is used in the derivation of some word (uselessness), examples, whether a CFL is finite (finiteness), example, whether the given string is generated by the given CFG (membership), example, parsing techniques, top down parsing, example Turing machine The mathematical models (FAs, TGs, PDAs) that have been discussed so far can decide whether a string is accepted or not by them . these models are language identifiers. However, there are still some languages which can’t be accepted by them . there does not exist any FA or TG or PDA accepting any non-CFLs. Alan Mathison Turing developed the machines called Turing machines, which accept some non-CFLs as well, in addition to CFLs. Turing machine Definition: A Turing machine (TM) consists of the following An alphabet of input letters. An input TAPE partitioned into cells, having infinite many locations in one .
đang nạp các trang xem trước
