- Computer Theory Need Help With This Outline 1 (131.99 KiB) Viewed 28 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.
1. Let G be the grammar: S SS (5) C 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 first. You will see below a sequence of steps in the proof, each with a reason left out. The proof is an induction on the number of steps in the derivation 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: One step. (1) The only 1-step derivation of a terminal string is S=> & because (2) E is in BP because Induction: An n-step derivation for some n>1. (3) The derivation Sw is either of the form (a) S>SS-1 w or of the form (b) S(S)-n-1 w because Case (a): (4) w-xy, for some strings x and y such that SP x and S9 y, where p<n and q<n because (5) x is in BP because m (6) y is in BP because (7) w is in BP because Case (b): (8) w = (z) for some string z such that S⇒n-1 z because (9) z is in BP because (10) w is in BP because 2. Let G be the grammar. S-551 (S) | E 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. NIY HAVE COMMENTED ON THOSE STEPS THAT
1. Let G be the grammar: S SS (5) C 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 first. You will see below a sequence of steps in the proof, each with a reason left out. The proof is an induction on the number of steps in the derivation 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: One step. (1) The only 1-step derivation of a terminal string is S=> & because (2) E is in BP because Induction: An n-step derivation for some n>1. (3) The derivation Sw is either of the form (a) S>SS-1 w or of the form (b) S(S)-n-1 w because Case (a): (4) w-xy, for some strings x and y such that SP x and S9 y, where p<n and q<n because (5) x is in BP because m (6) y is in BP because (7) w is in BP because Case (b): (8) w = (z) for some string z such that S⇒n-1 z because (9) z is in BP because (10) w is in BP because 2. Let G be the grammar. S-551 (S) | E 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. NIY HAVE COMMENTED ON THOSE STEPS THAT