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 # 23 Theory Of Automata By Dr. MM Alam 1 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 => bS (by PROD 2) => baS (by PROD 1) => baaS (by PROD 1) => 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 => bS => baS => babS => 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 Y → a Y → b 6 Context Free Language S → X S → y X | Lecture # 23 Theory Of Automata By Dr. MM Alam 1 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 => bS (by PROD 2) => baS (by PROD 1) => baaS (by PROD 1) => 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 => bS => baS => babS => 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 Y → a Y → b 6 Context Free Language S → X S → y X → ʎ Y→aY Y → bY Y → a Y → b All the words in this language are either of type X, if the first production in their derivation is S → X or of type Y, if the first production in their derivation is S → Y The only possible continuation for words of type X is the production X → ʎ Therefore ʎ is the only word of type X. 7 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 in the previous example except that the start symbol S has been replaced by the symbol Y. We can carry on from Y the same way we carried on from S before. This does not change the language generated, which contains only strings of terminals. 8 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 => aS => abS => ab ʎ = ab 10 Context
