Đang chuẩn bị liên kết để tải về tài liệu:
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) | 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) (terminal) . . . (terminal) (Nonterminal) 6 What are semi words? DEFINITION A CFG is called a regular grammar if each of its productions is of one of the two forms Nonterminal → semiword or Nonterminal → word 7 Semiwords Relationship between regular languages and context-free grammars? All regular languages can be generated by CFG's, and so can some nonregular languages but not all possible languages. Some regular languages can be generated by CFG's and some regular languages cannot be generated by CFG's. Some nonregular languages can be generated by CFG's and some nonregular languages cannot. 8 FA Conversion to Regular grammar Accepts the language of all words with a double a: S →aM S →bS M →aF M →bS F →aF F →bF F →ʎ 9 FA Conversion to Regular grammar Example 1 The word babbaaba is Accepted by FA Through sequence of this semi paths. 10 S S→bS bS S→aM baM M→bS babS S→bS babbS S→aM babbaM M→aF babbaaF F→bF babbaabF F→aF babbaabaF F→λ babbaaba FA Conversion to Regular grammar Example .