1. Lecture # 23 Theory Of Automata By Dr. MM Alam 1
  2. 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
  3. 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
  4. 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
  5. Context Free Language • Example 3 • Productions 3 and 4 can be used only once and only one of them can be used. • E.g, to generate babb we apply in order Prods 2, 1, 2, 4, as below: S => bS => baS => babS => babb 5
  6. 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
  7. 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
  8. 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
  9. 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
  10. Context Free Language S → aS S → bS S→ a S→ b S→ʎ • The word ab can be generated by the derivation S => aS => abS 10
  11. Context Free Language • Example 5 • or by the derivation S => aS => 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
  12. 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
  13. 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
  14. Context Free Language Example 7 • Let the terminals be a and b, nonterminals be S, X, and Y the productions be S → XY X → aX X → bX X→ a Y → Ya Y → Yb 14
  15. Context Free Language Example 7 • What can be derived from X? Let us look at the X productions alone. X → aX X → bX X→ a • X => bX => baX => babX => babbX => babba 15
  16. Context Free Language Example 7 • Similarly, the words that can be derived from Y are exactly those that begin with an a. • To derive abbab, Y => Yb => Yab => Ybab => Ybbab => abbab 16
  17. Tree format for CFG • In old-fashioned English grammar courses students were often asked to diagram a sentence. • They were to draw a parse tree, which is a picture with the base line divided into subject and predicate. 17
  18. Trees • Start with the symbol S. • Every time a production is used to replace a nonterminal by a string, draw downward lines from the nonterminal to each character in the string. • The CFG S → AA A → AAA I bA I Ab I a • Tree of this CFG is on next slide 18
  19. Trees S → AA A → AAA I bA I Ab I a 19
  20. Trees • We begin with S and apply the production S → AA. • To the left-hand A the production A → bA is applied. • To the right-hand A apply A → AAA is applied. • The b that we have on the bottom line is a terminal, so it does not descend further. • In the terminology of trees it is called a terminal node. 20