only)
- Automata And Formal Languages Answer Problem 1 Only 1 (249.79 KiB) Viewed 29 times
Automata and Formal Languages (Answer Problem 1 only)
-
answerhappygod
- Site Admin
- Posts: 899603
- Joined: Mon Aug 02, 2021 8:13 am
Automata and Formal Languages (Answer Problem 1 only)
Automata and Formal Languages (Answer Problem 1
only)
NOTES: A grammar is ambiguous if there are two different derivations for a certain string in the language of the grammar. This means, 2 different leftmost derivation sequences or 2 different derivation trees correspond to the string. Two leftmost derivation sequences are different if they involve different nonterminal symbols in corresponding sentential forms after always replacing the leftmost nonterminal. Two derivation trees are different if they have different structures or if they have the same structures but there are corresponding nodes with different labels. Hence, to determine if a formal grammar is ambiguous, you need to show 2 different derivation sequences or 2 different derivation trees for a one string that belongs to the language of the formal grammar. Draw the derivation sequences and compare corresponding sentential forms ( Compare the first sentential forms in the sequence, compare the 2nd sentential forms in the sequence, etc.) In practice, ambiguous grammars must be avoided. The meaning of a string is based on its derivation sequence or derivation tree. If a string has more than one derivation sequences, the string will have more than one meaning. (e.g. If a program statement corresponds to 2 derivation trees, the program statement has 2 possible meanings. For a program, a statement should always have one meaning.) I. (Problem 1) Suppose a formal grammar has the following components. N = {A,B} T = {0,1} P= { 2 →A, A → BO, A → AO, B → BO, A+ 1, B+1} REQUIRED: Use the string 1000 to verify that the formal grammar is ambiguous. (i.e. Show 2 different derivation sequences for 1000 or show 2 different derivation trees for 100.) II. (Problem 2) Suppose a formal grammar has the following components. N = {A} T ={0,1) P= {→ A, A → AOA, A+ 1} REQUIRED: Use the string 10101 to verify if the grammar is ambiguous or not. If it is ambiguous, present 2 leftmost derivation sequences for 10101 or present 2 derivation trees for 10101.
only)
NOTES: A grammar is ambiguous if there are two different derivations for a certain string in the language of the grammar. This means, 2 different leftmost derivation sequences or 2 different derivation trees correspond to the string. Two leftmost derivation sequences are different if they involve different nonterminal symbols in corresponding sentential forms after always replacing the leftmost nonterminal. Two derivation trees are different if they have different structures or if they have the same structures but there are corresponding nodes with different labels. Hence, to determine if a formal grammar is ambiguous, you need to show 2 different derivation sequences or 2 different derivation trees for a one string that belongs to the language of the formal grammar. Draw the derivation sequences and compare corresponding sentential forms ( Compare the first sentential forms in the sequence, compare the 2nd sentential forms in the sequence, etc.) In practice, ambiguous grammars must be avoided. The meaning of a string is based on its derivation sequence or derivation tree. If a string has more than one derivation sequences, the string will have more than one meaning. (e.g. If a program statement corresponds to 2 derivation trees, the program statement has 2 possible meanings. For a program, a statement should always have one meaning.) I. (Problem 1) Suppose a formal grammar has the following components. N = {A,B} T = {0,1} P= { 2 →A, A → BO, A → AO, B → BO, A+ 1, B+1} REQUIRED: Use the string 1000 to verify that the formal grammar is ambiguous. (i.e. Show 2 different derivation sequences for 1000 or show 2 different derivation trees for 100.) II. (Problem 2) Suppose a formal grammar has the following components. N = {A} T ={0,1) P= {→ A, A → AOA, A+ 1} REQUIRED: Use the string 10101 to verify if the grammar is ambiguous or not. If it is ambiguous, present 2 leftmost derivation sequences for 10101 or present 2 derivation trees for 10101.