tailieunhanh - Lecture note Theory of automata - Lecture 14

This chapter presents the following content: Examples of Kleene’s theorem part III (method 1) continued, Kleene’s theorem part III (method 2: Concatenation of FAs), examples of Kleene’s theorem part III (method 2: concatenation FAs) continued, Kleene’s theorem part III (method 3: closure of an FA), examples of Kleene’s theorem part III (method 3: Closure of an FA) continued. | Lecture note Theory of automata - Lecture 14 Lecture 23 Theory Of Automata By Dr. MM Alam 1 Lecture 22 Recap . Introduction to Context Free Grammars How a High Level language is converted to low level instructions that computer understand. What are Production Rules and Derivations What is a CFG CFG Examples JFLAP for CFG Context Free Language Example 3 Let the terminals be a and b the only nonterminal be S and Productions PROD 1 S aS PROD 2 S bS PROD 3 S a PROD 4 S b 3 Context Free Language Example 3 The word baab can be produced as follows S gt bS by PROD 2 gt baS by PROD 1 gt baaS by PROD 1 gt baab by PROD 4 4 Context Free Language Example 3 Productions 3 and 4 can be used only once and only one of them can be used. to generate babb we apply in order Prods 2 1 2 4 as below S gt bS gt baS gt babS gt babb 5 Context Free Language Example 4 Let the terminals be a and b nonterminals be S X and Y. The productions are S X S y X ʎ Y aY Y bY 6 Context Free Language S X S y X ʎ Y aY Y bY Y a Y b 7 All the words in this language are either Context Free Language S X S y X ʎ Y aY Y bY Y a Y b The productions whose left side is Y form a collection identical to the productions 8 in Context Free Language Example 5 Let the terminals be a and b. Let the only nonterminal be S. Let the productions be S aS S bS S a S b S ʎ 9 Context Free Language S aS S bS S a S b S ʎ The word ab can be generated by the derivation S gt aS gt abS 10 Context Free Language Example 5 or by the derivation S gt aS gt ab The language of this CFG is also a b but the sequence of productions that is used to generate a specific word is not unique. 11 Context Free Language Example 6 Let the terminals be a and b nonterminals be S and X and the productions be S XaaX X aX X bX X a X b 12 Context Free Language S XaaX X aX X bX X a X b If the nonterminal X appears in any working string we can apply productions to turn it into any word we want. Therefore the words generated 13 from S Context Free Language .