- Computer Theory Need Help With This Outline 1 (133.45 KiB) Viewed 35 times
Computer Theory. Need help with this outline.
-
answerhappygod
- Site Admin
- Posts: 899603
- Joined: Mon Aug 02, 2021 8:13 am
Computer Theory. Need help with this outline.
Computer Theory. Need help with this outline.
4. a. [10 pts] Simplify the grammar of question 3 according to the summary given by Theorem 7.14. b. [10 pts] The grammar of question 3 can be put into the following CNF, where all variables have been renamed to mask their origin after eliminating redundant variables and productions: Z XaY1 | XaY2 1 XaY3 I XaXb | XbY4 | XbY5 | XbY6 | XbXa Y1 - 2Y2 Y2 - Xbz Y3 - ZXb Y4 - ZY5 Y5 - XaZ Y6 - ZXa Xa - a Xb - b Show the step-by-step transformation of your answer for a into Chomsky Normal Form. 5. a. [15 pts] Using the CNF in part b of question 4, use the CYK table-filling algorithm to show the membership of the string ababba in the language. b. [5 pts] Give a parse tree for the string ababba according to the CNF in part b of question 4.
4. a. [10 pts] Simplify the grammar of question 3 according to the summary given by Theorem 7.14. b. [10 pts] The grammar of question 3 can be put into the following CNF, where all variables have been renamed to mask their origin after eliminating redundant variables and productions: Z XaY1 | XaY2 1 XaY3 I XaXb | XbY4 | XbY5 | XbY6 | XbXa Y1 - 2Y2 Y2 - Xbz Y3 - ZXb Y4 - ZY5 Y5 - XaZ Y6 - ZXa Xa - a Xb - b Show the step-by-step transformation of your answer for a into Chomsky Normal Form. 5. a. [15 pts] Using the CNF in part b of question 4, use the CYK table-filling algorithm to show the membership of the string ababba in the language. b. [5 pts] Give a parse tree for the string ababba according to the CNF in part b of question 4.