TAILIEUCHUNG - Lecture note Theory of automata - Lecture 15

After studying this chapter you will be able to understand: Examples of Kleene’s theorem part III (method 3), NFA, examples, avoiding loop using NFA, example, converting FA to NFA, examples, applying an NFA on an example of maze. | Lecture # 24 Theory Of Automata By Dr. MM Alam 1 1 Lecture#23 Summary CFG Examples Introduction to Trees Ambiguity in CFGs CFG in JFLAP Unrestricted Grammars Unrestricted Grammars: An unrestricted grammar is similar to a context-free grammar (CFG), except that the left side of a production may contain any nonempty string of terminals and variables, rather than just a single variable. In a CFG, the single variable on the left side of a production could be expanded in a derivation step. In an unrestricted grammar, multiple variables and/or terminals that match the left-side of a production can be expanded by the right-side of that production. 3 Unrestricted Grammar Example S AX Db bD A aAbc DX EXc A aBbc BX ʎ Bb bB cE Ec 4 CFG with JFLAP Unrestricted Grammar with JFLAP User Controlled Parsing with JFLAP 5 Semi words Definition For a given CFG a semiword is a string of terminals (maybe none) concatenated with exactly one nonterminal (on the right), for example, (terminal)

• Tự động hoá
• Theory of automata
• Lecture Theory of automata
• Computer theory
• Theory of computation
• Kleene’s theorem part III
• Nondeterministic finite automaton
• Automata theory
• Automata theory languages
• Automata theory computation
• Pushdown automata
• Context Free grammars
• Regular languages
• Additional classes
• Intractable problems
• Properties of context free languages
• Solution of the task
• Polish notation
• Total language tree
• Null production
• Nullable production
• Theorem regarding CNF
• The START state
• Nondeterministic PDA
• Equivalent PDA
• PDA corresponding to CFG
• STACK alphabet
• Computer science
• CFG corresponding
• Conversion form of PDA
• Recap of PDA
• Non context free language
• Parsing techniques
• Turing machine
• DELETE subprogram
• Kleene’s theorem
• NFA corresponding
• Concatenation of FAs
• Distinguishable strings
• Indistinguishable strings
• Recap theorem
• Moore machine
• Mealy machine
• Applications of complementing
• Equivalent machines
• Mealy machines
• Complement of a language
• Non regular language
• Example of nonregular language
• Pumping lemma version I