Lefmost rightmost TOC.pptx

Table of Contents (TOC) is a list of the headings or sections in a document, typically found at the beginning of the document. The TOC provides a quick reference for the reader to navigate to the specific section they are interested in reading.

In terms of grammar, TOCs often use parallel structure to list the headings and subheadings, such as using bullet points or numbered lists. In addition, TOCs may also use capitalization, bold or italic formatting to indicate the level of the heading or subheading.

A typical TOC structure is to start with the main heading, followed by subheadings and sub-subheadings. For example, the main heading may be "Introduction," followed by subheadings "Background," "Purpose," and "Methodology." Each subheading may then have sub-subheadings, such as "Background" having sub-subheadings "Historical context" and "Recent developments."

It's important to note that TOCs can vary depending on the type of document and the style guide being used. Some TOCs may use numbers, while others use bullet points. Additionally, some TOCs may include page numbers while others may not.

In summary, TOCs provide a quick reference for the reader to navigate the document, often using parallel structure, capitalization, and formatting to indicate the level of headings and subheadings. The structure and formatting of TOCs may vary depending on the type of document and style guide being used.

1. Department Of Computer Science And Application Atal Bihari Vajpayee Vishwavidayalaya ,Bilaspur (C.G.) SESSION :- 2022-2023 Subject- Theory Of Computing Presentation topic :- Context - Free Grammer PRESENTED TO - MISS PRERNA MAM Geeta Kumari Chandani Yamini Jankee MSc Ist Sem PRESENTED BY -

2. CONTENT - Context - Free Grammer Formal definition of CFG Derivation Leftmost Derivation Rightmost Derivation Derivation tree Ambiguity in Grammer

3. Context-Free Grammar (CFG) CFG stands for context-free grammar . It is a set of rules which is used to generate all possible patterns of strings in a given formal language. Context-free grammar G can be defined by four tuples as: G = (V, T, P, S)    G  is the grammar, which consists of a set of the production rule. It is used to generate the string of a language. T = set of Terminal symbols . It is denoted by small letters .

4. P = set of Production rules S = Start symbol EXAMPLE 1 : - Construct a CFG for the regular expression a* . production rules :- S a S rule 1 S ε  rule 2 V = set of Non - Terminal symbols . It is denoted by capital letters

5. If we want to derive a string “aaaa” , we can start with start symbol S a S rule 1 aa S rule 1 aaa S rule 1 aaaa S rule 1 aaaaε rule 2 aaaa . The r . e . = a* can generate a set of string {ε , a , aa , aaa,…..} . Solution :-

6. Production rules :- S S / 1 S S ε  SOLUTION :- the r . e . = (0+1)* can generate a set string { ε , 0 , 1 01 , 10 , 00 , 11 , ……..} . Construct a CFG for the regular expression (0+1)* . EXAMPLE 2 :-

7. Derivation Derivation is a sequence of production rules . It is used to get the input string through these production rules. During parsing, we have to take two decisions. These are as follows: We have to decide the non-terminal which is to be replaced. We have to decide the production rule by which the non-terminal will be replaced. We have two options to decide which non-terminal to be placed with production rule.

8. 1. Leftmost Derivation : In the leftmost derivation, the input is scanned and replaced with the production rule from left to right. So in leftmost derivation, we read the input string from left to right . Example: E = E + E   E = E - E   E = a | b   Input a - b + a 

9. The leftmost derivation is: E = E + E   E = E - E + E   E = a - E + E   E = a - b + E   E = a - b + a   2. Rightmost Derivation : In rightmost derivation, the input is scanned and replaced with the production rule from right to left. So in rightmost derivation, we read the input string from right to left .

10. Example :- Production rules: E  =  E  +  E    E  =  E  -  E    E  = a | b    Input a - b + a The rightmost derivation is : E  = E - E   E = E - E + E   E = E - E +  a    E  =  E  - b + a   E  = a - b + a

11.    When we use the leftmost derivation or rightmost derivation, we may get the same string. This type of derivation does not affect on getting of a string. Examples of Derivation: Example 1: Derive the string "abb" for leftmost derivation and rightmost derivation using a CFG given by, S  →  AB  | ε   A  → a B    B  →  S b  

12. Solution: Leftmost derivation: S AB aB B a Sb B a ε bB ab ε Sb ab ε b abb

13. Rightmost derivation:

14. Example 2: Derive the string "aabbabba" for leftmost derivation and rightmost derivation using a CFG given by, S  → a B  | b A    A  → a | a S  | b AA    B  → b | bS | a BB    Solution: Leftmost derivation: S    a B              S  → a B        aa BB            B  → a BB    aab B            B  → b   aabb S           B  → b S    aabba B          S  → a B    aabbab S         B  → b S    aabbabb A        S  → b A    aabbabba       A  → a  

15. Rightmost derivation: S    a B              S  → a B        aa BB            B  → a BB    aa B b S           B  → b S    aa B bb A          S  → b A    aa B bba         A  → a   aab S bba        B  → b S    aabb A bba       S  → b A   aabbabba       A  → a   Example 3: Derive the string "00101" for leftmost derivation and rightmost derivation using a CFG given by, S  →  A 1 B    A  → 0 A  | ε   B  → 0 B  | 1 B  | ε

16. Solution: Leftmost derivation: S    A 1 B    A 1 B    00 A 1 B    001 B    0010 B    00101 B    00101   Rightmost derivation: S    A 1 B    A 10 B    A 101B   A 101   A 101   00 A 101   00101  

17. Derivation Tree Derivation tree is a graphical representation for the derivation of the given production rules . It is the simple way to show how the derivation can be done to obtain some string from a given set of production rules. The derivation tree is also called a parse tree. A parse tree contains the following properties: The root node is always a node indicating start symbols. The derivation is read from left to right The leaf node is always terminal nodes. The interior nodes are always the non-terminal nodes.

18. Example 1: Production rules: E = E + E   E = E * E   E = a | b | c   Input a * b + c    Step 1:

19. Step 2: Step 3 :

20. Step 4: Step 5:

21. Example 2: Draw a derivation tree for the string "bbabb" from the CFG given by S  → b S b  S  a S b Solution: Now, the derivation tree for the string "bbabb" is as follows:

22. The above tree is a derivation tree drawn for deriving a string bbabb . By simply reading the leaf nodes, we can obtain the desired string. The same tree can also be denoted by,

23. Ambiguity in Grammar A grammar is said to be ambiguous if there exists more than one leftmost derivation or more than one rightmost derivation or more than one parse tree for the given input string. If the grammar is not ambiguous , then it is called unambiguous. Example 1:- Let us consider a grammar G with the production rule S S a S a S S a

24. Solution :- For given grammer there are two ways to derive a string “aaa” S S a S a a S S a a S a First Leftmost Derivation Second Leftmost Derivation Since there are two leftmost derivation for a single sting “aaa” , the grammer is Ambigous grammer .

25. Example 2 :- Check whether the given grammar G is ambiguous or not. E  →  E  +  E    E  →  E  -  E    E  → id   Solution :- From the above grammar String "id + id - id" can be derived in 2 ways:

26. First Leftmost derivation E → E + E       → id +  E       → id +  E - E       → id + id -  E       → id + id- id   Second Leftmost derivation E  →  E - E      → E + E  -  E       → id +  E  -  E       → id + id -  E       → id + id - id   Since there are two leftmost derivation for a single string "id + id - id", the grammar G is ambiguous .

27. EXAMPLE 3 :- Check whether the given grammer is ambigous or not . S AB A a A / b B b B / a Solution :- S A B a A b B b b There are only one derivatio tree form for given grammer ,so this grammer is Unambigous grammer .

28. Check whether the given grammer is Ambigous or not ? 1. G : E E + E E id W : id + id + id 2. G : S AB / aa B A a / A a B b W : “aab” 3. G : S a S a S b S b S ε  W : “abba”

29. THANK YOU