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 note Theory of automata - Lecture 15 Lecture 24 Theory Of Automata By Dr. MM Alam 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 be3 expanded 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 1. All regular languages can be generated by CFG s and so can some nonregular languages but not all possible languages. 2. 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 9 FA Conversion to Regular grammar Example 1 The word babbaaba is S Accepted by FA Through S bS bS S aM baM sequence of this semi paths. M bS babS S bS babbS S aM babbaM M aF babbaaF F bF babbaabF F aF babbaabaF F λ babbaaba 10 FA Conversion to Regular grammar Example The language of all words with an even number of
