2.4 derivations and languages

Derivations and Languages. Recursive Inference. Derivation. Example problem

1. Derivations and Languages Sampath Kumar S, AP/CSE, SECE

2. Derivations and Languages While inferring whether the given input strings belongs to the given CFG, we can have 2 approaches: Using the rules from body to head ( Recursive Inference ) Using the rules from head to body ( Derivation ) 8/3/2016 Sampath Kumar S, AP/CSE, SECE 2 Derivation using Grammar Recursive Inference Derivation Left Most Derivation Right Most Derivation

3. Recursive Inference: Here we take string from each variables, concatenate them in proper order and infer that the resulting string is in the language of the variable in the head 8/3/2016 3 Sampath Kumar S, AP/CSE, SECE

4. Derivation: Here we use the production from head to body i.e., from start symbol expanding till reaches the given string. This use of grammar is called derivation. 8/3/2016 4 Sampath Kumar S, AP/CSE, SECE

5. Problems to discuss: For the language L = { wcw R | w (0+1)*} check whether the string 01c10 belongs to the language L or not. Solution: Step 1: For the language L, the productions are S → 0S0 | 1S1 | C Step 2: Derivation S → 0S0 [ ∵ S → 0S0] → 01E10 [ ∵ S → 1S1] → 01c10 [ ∵ S → c] 8/3/2016 Sampath Kumar S, AP/CSE, SECE 5

6. Understanding the Language defined by CFG: The only way to recognize the language, is to try out various strings from the given production rules. Then by observing the derived strings, one can find out the language generated from the given CFG. 8/3/2016 Sampath Kumar S, AP/CSE, SECE 6

7. Problems to discuss: Derive ‘a 4 ’ from the grammar G=({S}, {a},P,S) where P: S → aS | ε . Find L(G) and derive the string ‘ abbab ’ for the grammar G=({S}, {a},P,S) where P: S → aS|bS|a|b. Find L(G) and derive the string ‘ abbaaba ’ for the grammar G=({S,X}, {a},P,S) where P: S → XaaX, X → aX|bX| ε . Find L(G) for the grammar G=({S,C}, {a,b},P,S) where P is given by S → aCa, C → aCa|b. 8/3/2016 Sampath Kumar S, AP/CSE, SECE 7

8. Solution: L = ( a+b )* L = ( a+b )* aa ( a+b )* L= {a n ba n for n > 1} 8/3/2016 Sampath Kumar S, AP/CSE, SECE 8

9. Leftmost and Rightmost Derivation: If a word w is generated by a CFG by a certain derivation and at each step in the derivation, a rule of production is applied to the leftmost non terminal in the working string, then this derivation is called leftmost derivation (LMD). If a word w is generated by a CFG by a certain derivation and at each step in the derivation, a rule of production is applied to the rightmost non terminal in the working string, then this derivation is called rightmost derivation (RMD). 8/3/2016 Sampath Kumar S, AP/CSE, SECE 9

10. Problems to discuss: Consider the CFG ({S,X}, {a,b}, P, S} where productions are S → baXaS|ab, X →Xab|aa. Find the LMD and RMD for the string w= baaaababaab . Consider the CFG S → aB|bA A → a | aS | bAA B → b | bS | aBB Find the LMD and RMD for the string W= aabbabba . 8/3/2016 Sampath Kumar S, AP/CSE, SECE 10

11. Derivation Tree: A derivation tree or parse tree is an ordered rooted tree that graphically represents the semantic information a string derived from a Context - Free Grammar. 8/3/2016 Sampath Kumar S, AP/CSE, SECE 11

12. Representation Technique Root vertex  − Must be labeled by the start symbol. Vertex  − Labeled by a non-terminal symbol. Leaves  − Labeled by a terminal symbol or ε. If S → x 1 x 2  …… x n  is a production rule in a CFG, then the parse tree / derivation tree will be as follows − 8/3/2016 Sampath Kumar S, AP/CSE, SECE 12

13. Approaches for constructing Derivation Tree: There are two different approaches to draw a derivation tree − Top-down Approach − Starts with the starting symbol  S Goes down to tree leaves using productions Bottom-up Approach − Starts from tree leaves Proceeds upward to the root which is the starting symbol  S 8/3/2016 Sampath Kumar S, AP/CSE, SECE 13

14. Derivation or Yield of a Tree: The derivation or the yield of a parse tree is the final string obtained by concatenating the labels of the leaves of the tree from left to right, ignoring the Nulls. However , if all the leaves are Null, derivation is Null. 8/3/2016 Sampath Kumar S, AP/CSE, SECE 14

15. Sentential Form and Partial Derivation Tree: A partial derivation tree is a sub-tree of a derivation tree/parse tree such that either all of its children are in the sub-tree or none of them are in the sub-tree. 8/3/2016 Sampath Kumar S, AP/CSE, SECE 15

16. Leftmost and Rightmost Derivation of a String Leftmost derivation  − A leftmost derivation is obtained by applying production to the leftmost variable in each step. Rightmost derivation  − A rightmost derivation is obtained by applying production to the rightmost variable in each step. 8/3/2016 Sampath Kumar S, AP/CSE, SECE 16

17. Left and Right Recursive Grammars In a context-free grammar  G , if there is a production in the form  X → Xa , where   X  is a non-terminal and  ‘a’  is a string of terminals, it is called a  left recursive production . The grammar having a left recursive production is called a  left recursive grammar . If in a context-free grammar  G , if there is a production is in the form  X → aX  where  X  is a non-terminal and  ‘a’  is a string of terminals, it is called a  right recursive production . The grammar having a right recursive production is called a  right recursive grammar . 8/3/2016 Sampath Kumar S, AP/CSE, SECE 17

18. Problems to discuss: 68. Let a CFG G= { { S}, { a, b}, P, S} Where P = S → SS | aSb | ε . Draw derivation tree for the string “ abaabb ” One derivation form of the above CFG is S → S S → a S bS → ab S → aba S b → abaa S bb → abaabb 8/3/2016 Sampath Kumar S, AP/CSE, SECE 18

19. Problems to discuss: 69. Let any set of production rules in a CFG be X → X+X | X*X |X| a over an alphabet {a }. Find LMD and RMD for string " a+a *a“. 70. Construct Parse tree for the string a*(a+b00) for the following CFG using left and right most derivation. E → A | E + E | E * E | (E) A → a | b | Aa | Ab | A0 | A1 71. Construct Parse tree for the string a*( a+a ) for the following CFG using left and right most derivation. E → E + E | E * E | (E ) | a 8/3/2016 Sampath Kumar S, AP/CSE, SECE 19

20. Problems to discuss: 72. Generate parse tree for the string 00101 using left and right most derivation for following CFG S → A1B, A → 0A| ε | B → 0B | 1B | ε 73. Generate parse tree for the string babbab using left and right most derivation for following CFG S → aSa | bSb | a |b | ε 8/3/2016 Sampath Kumar S, AP/CSE, SECE 20

21. 8/3/2016 Sampath Kumar S, AP/CSE, SECE 21