Understanding Derivation Trees and Regular Languages in Formal Language Theory
Derivation trees play a crucial role in formal language theory, aiding in visualizing the process of deriving strings from a formal grammar. The concept of leftmost and rightmost derivations, along with their respective tree representations, provide insights into how strings are generated using grammatical rules. Explore these fundamental concepts in regular languages to deepen your understanding of computational linguistics.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Derivation Trees And Regular Languages
Derivation Trees The process of deriving a string is called as derivation. The geometrical representation of a derivation is called as a parse tree or derivation tree. In a derivation tree, the root is the start variable, all internal nodes are labeled with variables, while all leaves are labeled with terminals. The children of an internal node are labeled from left to right with the right-hand side of the production used.
Types of Derivation Types of Derivation Leftmost Derivation Rightmost Derivation
1. Leftmost Derivation- The process of deriving a string by expanding the leftmost non-terminal at each step is called as leftmost derivation. The geometrical representation of leftmost derivation is called as a leftmost derivation tree.
Example- S aB / bA S aS / bAA / a B bS / aBB / b (Unambiguous Grammar) Let us consider a string w = aaabbabbba Now, let us derive the string w using leftmost derivation. Leftmost Derivation- S aB aaBB (Using B aBB) aaaBBB (Using B aBB) aaabBB (Using B b) aaabbB (Using B b) aaabbaBB (Using B aBB) aaabbabB (Using B b) aaabbabbS (Using B bS) aaabbabbbA(Using S bA) aaabbabbba(Using A a)
Leftmost Derivation Tree S a B a B B a B B a B B b b b b S b A a
2. Rightmost Derivation- The process of deriving a string by expanding the rightmost non-terminal at each step is called as rightmost derivation. The geometrical representation of rightmost derivation is called as a rightmost derivation tree.
Example- Consider the following grammar- S aB / bA S aS / bAA / a B bS / aBB / b (Unambiguous Grammar) Let us consider a string w = aaabbabbba Now, let us derive the string w using rightmost derivation. Rightmost Derivation- S aB aaBB (Using B aBB) aaBaBB (Using B aBB) aaBaBbS (Using B bS) aaBaBbbA(Using S bA) aaBaBbba (Using A a) aaBabbba (Using B b) aaaBBabbba (Using B aBB) aaaBbabbba (Using B b) aaabbabbba(Using B b)
Rightmost Derivation Tree S a B a B B a B B a B B b b b b S b A a
Ambiguous Grammars A grammar is unambiguous if there is a unique leftmost derivation for each string in the language. Equivalently, for each string there is a unique derivation tree. For example, our grammar for equality is ambiguous: S 0S1S | 1S0S | (The string 0101 has two derivation trees.)
Grammars and Compilers Grammars are used in compilers. A compiler checks that the input file is valid by essentially finding the derivation tree. This derivation tree is then used in finding code for the file or expression. If grammar is unambiguous, the derivation tree is always unique.
Grammar for Arithmetic The language of arithmetical expressions using only multiplication and addition can be described as the following CFG with start variable E: E E+T | T T T F | F F (E) | number (Think of Expression, Factor and Term.) This generates expressions such as 1+(3+2) 5 and 1+2 3.
Derivation Tree The derivation tree for 1+2 3: E E + T T T * F F F 3 1 2 Note that derivation tree automatically knows that multiplication takes precedence over addition. Goddard 6b:
Summary Each string in the language has a leftmost derivation and a derivation tree. If these are unique for all strings, then the grammar is called unambiguous.
