- Computer Theory Need Help With This Outline 1 (104 KiB) Viewed 32 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.
2. Let G be the grammar. S SS 1 (S) 1 € L(G) is the language BP of all strings of balanced parentheses, that is, those strings that could appear in a well-formed arithmetic expression. We want to prove that L(G) = BP, which requires two inductive proofs: 1. If w is in L(G), then w is in BP. 2. If w is in BP. then w is in L(G). We shall here prove only the second. You will see below a sequence of steps in the proof, each with a reason left out. The proof is an induction on the length of w. You must give a reason for each step, IN YOUR OWN CONCISE AND RELEVANT WORDS - as long as you write so. the reason at each step need not be more than one grammatically-correct sentence, or between one and three short grammatically-correct clauses. None of the reasons require elaborate explanations or the use of examples. As such, reasons that go on for many lines may be dismissed out of hand. NOTE: This problem appeared in the homework, where you were only required to classify the general reason. You must now write in the precise reason yourself. IF YOU DID THIS ON YOUR SCRAP WORK, I MAY ONLY HAVE COMMENTED ON THOSE STEPS THAT RELATED TO THE CHOICES PRESENTED, so do not take any lack of comments as indication that your work was correct. Basis: Length = 0. (1) The only string of length 0 in BP is a because (2) E is in L(G) because Induction: w=n>0. (3) w is of the form (x)y, where (x) is the shortest proper prefix of w that is in BP, and y is the remainder of w because (4) x is in BP because (5) y is in BP because (6) x <n because (7) y<n because (8) x is in L(G) because (9) y is in L(G) because (10) (x) is in L(G) because (11) w is in L(G) because nomm
2. Let G be the grammar. S SS 1 (S) 1 € L(G) is the language BP of all strings of balanced parentheses, that is, those strings that could appear in a well-formed arithmetic expression. We want to prove that L(G) = BP, which requires two inductive proofs: 1. If w is in L(G), then w is in BP. 2. If w is in BP. then w is in L(G). We shall here prove only the second. You will see below a sequence of steps in the proof, each with a reason left out. The proof is an induction on the length of w. You must give a reason for each step, IN YOUR OWN CONCISE AND RELEVANT WORDS - as long as you write so. the reason at each step need not be more than one grammatically-correct sentence, or between one and three short grammatically-correct clauses. None of the reasons require elaborate explanations or the use of examples. As such, reasons that go on for many lines may be dismissed out of hand. NOTE: This problem appeared in the homework, where you were only required to classify the general reason. You must now write in the precise reason yourself. IF YOU DID THIS ON YOUR SCRAP WORK, I MAY ONLY HAVE COMMENTED ON THOSE STEPS THAT RELATED TO THE CHOICES PRESENTED, so do not take any lack of comments as indication that your work was correct. Basis: Length = 0. (1) The only string of length 0 in BP is a because (2) E is in L(G) because Induction: w=n>0. (3) w is of the form (x)y, where (x) is the shortest proper prefix of w that is in BP, and y is the remainder of w because (4) x is in BP because (5) y is in BP because (6) x <n because (7) y<n because (8) x is in L(G) because (9) y is in L(G) because (10) (x) is in L(G) because (11) w is in L(G) because nomm