Formal Language Automata
Questions & Answers
Problem 1 (23 pts.) Consider the following claim: Claim. {21n: n € Z} U {14n: n € Z} c{7n:n €Z}. (a) (3 pts.) Write the claim as an (equivalent) if-then statement. Grading Notes. While a detailed rubric cannot be provided in advance as it gives away solution details, the following is a general idea of how points are distributed for this problem. We give partial credit where we can. (3) Correctness. Regardless of how you formulate your proof, you will need to have an if-then statement that is equivalent to the original. (b) (11 pts.) Give a direct proof by cases that the claim is true. As a hint, you might want to prove the if-then statement you constructed in (a). To get full points you must use a mixture of formal notation and word explanations (e.g. the "column" format). Each step of your proof should have an explanation as to how/why you could make that logical step. When in doubt, more detail is better than less. Grading Notes. While a detailed rubric cannot be provided in advance as it gives away solution details, the following is a general idea of how points are distributed for this problem. If you can at least get part-way, we give partial credit where we can. (9) Correctness. If your proof is not correct, this is where you'll get docked. (2) Regardless of how you formulate your proof, you will need clearly labeled exhaustive cases. (6) Regardless of how you formulate your proof, somewhere you'll need certain facts without which the proof wouldn't work. E.g. if it weren't true that the sum of two integers is integer, would your proof fail? If so, then that is a fact I need to see stated somewhere. (1) The order of these facts makes sense, so that you're not inferring something before you have all the facts to infer it. E.g. you cannot use the fact that the sum of two integers is integer if you don't already know that you have two integers to begin with. The order of how you use these does not have to exactly match those in the sample solutions, but there are orders that will not work and you will lose points if, for example, you use "the difference of ints is int" before you use "the product of ints is int". If you combine some steps (such as "the difference and product of ints is int" or "the product of two non-zero ints is a non-zero int") that is fine. Just don't combine all (see below). (2) Communication. We need to see a mix of notation and intuition, preferably in the "column" format with the notation on the left, and the reasons on the right. If you skip too many steps at once, or we cannot follow your proof, or if your solution is overly wordy or confusing, this is where you'll get docked. (c) (3 pts.) State (but do not prove) the contrapositive of your statement from part (a). Grading Notes. While a detailed rubric cannot be provided in advance as it gives away solution details, the following is a general idea of how points are distributed for this problem. We give partial credit where we can. (3) Correctness. You have to have the contrapositive statement of whatever if-then state- ment you wrote in part (a). (d) (3 pts.) State (but do not prove) the converse of your statement from part (a). Grading Notes. While a detailed rubric cannot be provided in advance as it gives away solution details, the following is a general idea of how points are distributed for this problem. We give partial credit where we can. (3) Correctness. Regardless of how you formulate your proof, you will need to have an if-then statement that is the contrapositive of the original. (e) (3 pts.) Give a disproof by counter-example of the converse from part (d). (That is, show that the converse is not true by providing an example that demonstrates it is not true.) Remember that any disproof by counter-example not only provides the counter-example, but also an explanation as to why it is a counter-example. Grading Notes. Note that this problem gives you practice disproving a statement by counter-example, which requires clearly stating a counter-example, and then showing why it is a counter-example.
Problem 2 (13 pts.) Consider the following claim. Claim. For any sets S and T, (SxT)n (Tx S)-(Sx S) = 0. (a) (11 pts.) Use a proof by contradiction to prove the claim. To get full points you must use a mixture of formal notation and word explanations (e.g. the "column" format). Each step of your proof should have an explanation as to how/why you could make that logical step. When in doubt, more detail is better than less. Grading Notes. While a detailed rubric cannot be provided in advance as it gives away solution details, the following is a general idea of how points are distributed for this problem. We give partial credit where we can. (9) Correctness. If your proof is not correct, this is where you'll get docked. (5) Regardless of how you formulate your proof, somewhere you'll need certain facts without which the proof wouldn't work. E.g. if it weren't true that the sum of two integers is integer, would your proof fail? If so, then that is a fact I need to see stated somewhere. (1) The order of these facts must make sense, so that you're not inferring something before you have all the facts to infer it. E.g. you cannot use the fact that the sum of two integers is integer if you don't already know that you have two integers to begin with. (3) You also must use a proof by contradiction, which clearly states it is a proof by contradiction, states what the contradictory assumption is, finds a contradiction, and clearly states what and where that contradiction is. (2) Communication. We need to see a mix of notation and intuition, preferably in the "column" format with the notation on the left, and the reasons on the right. If you skip too many steps at once, or we cannot follow your proof, or if your solution is overly wordy or confusing, this is where you'll get docked. (b) (2 pts.) Is it possible to prove this claim by contrapositive? If so, what would the statement of the claim be (that you could then apply the contrapositive to)? If not, give a brief explanation why it cannot be done. Grading Notes. This problem is meant for you to think about whether you can modify your proof to be of a different form, and explaining your answer.
2- Given a figure of a 3x8 decoder built using three 1x2 decoders, which is the correct order of input signals to assure correct operation? a. XYZ → Y1,Y2,Y3 b. ZXY → Y1,Y2,Y3 c. YZX → Y1,Y2,Y3 d. YZX → Y1,Y2,Y3
5- Given figure of 3x8 decoder built with 1x2 decoders. What are the correct signals for operation? (similar to this figure) A. YXZ → Y1,Y2,Y3 B. ZXY → Y1,Y2,Y3 C. ZYX → Y1,Y2,Y3 D. XYZ → Y1,Y2,Y3
13- What is the operation of the following truth table? A. T flip flop B. JK flip flop C. SR flip flop
3. Construct a PDA that accepts the following languages: a) L = {anb2n: n≥1} b) L = {aibi: izj.j≥ 1}
4. (a) Write a grammar for the following language consisting of strings that have n copies of the letter 'a' followed by one more number of copies of the letter 'b', where n > 0. Examples of such strings are abb, aabbb, etc, but a, ab, ba, and aaabb are not. (b) Draw parse trees for the sentences abb and aabbb in Problem 4.
2. Show a (i) parse tree, (ii) left most derivation and (ii) right most derivation for the following ambiguous Grammar: Here, S can be called as a Start variable which is related to A, B, where A and B are other variables which yield terminal symbols like a, b • Construct an ambiguous string for the problem. S→ aB | bA S→ aS | bAA |a B→ bS | aBB | b
:) Consider the grammar below for floating point numbers: (20pt) Using the above grammar, write an attribute grammar which contains an attribute val that stores the value of a number such that the val of any internal node is the sum of the val's of its children. Besides the val attribute, you can use only one other attribute. The grammar does not have to be L-attributed. (10pt) Draw the annotated parse tree for the string 12.34. Show the attribute flow (arrows and values).
(30pt) Expressions can be written without the need of parentheses in postfix form (also called reverse Polish notation). The name comes from the fact that the operator comes after the operands: a+bis written as ab+. A postfix expression can be easily evaluated using a stack. (a) (10pt) Using the underlying grammar from Fig. 4.1, write an S-attributed grammar that associates with the root of the parse tree the postfix expression corresponding to the (infix)expression produced by the tree. (b) (5pt) Use this S-attributed attributed grammar to draw the annotated parse tree for the expression (- 3 + 2) * 7 - 1. Show the attribute flow (arrows and values). (c) (10pt) Using the underlying grammar from Fig. 4.3, write an L-attributed grammar that associates with the root of the parse tree the postfix expression corresponding to the (infix)expression produced by the tree. (d) (5pt) Use this L-attributed attributed grammar to draw the annotated parse tree for the expression (- 3 + 2) * 7 - 1. Show the attribute flow (arrows and values).
) Consider the language: ) (10pt) Construct a grammar, G₁, for P that is LL(1). Build its LL(1) parse table (as inFig. 2.20) to prove that it is LL(1). (10pt) Construct a grammar, G2, for P that is SLR(1) but not LL(1). Build its SLR(1) parsetable (as in Fig. 2.28) to prove that it is SLR(1). Prove also that it is not LL(1). Construct a grammar, G3, for P that is not SLR(1). Prove that it is not SLR(1). ) Show the parse tree and the left derivation for the string [([]) ()]$$ in G₁. ›) (4pt) Show the trace of the table-driven LL(1) parse (as in Fig. 2.21) using G₁ for the samestring. ) Show the parse tree and the right derivation for the string [([]) ()]$$ in G₂. (4pt) Show the trace of the table-driven SLR(1) parse (as in Fig. 2.30) using G₂ for the same string. The grammars G₁..3 above must have a production P → S$$, with P not appearing anywhere else in the grammar. The parse tables are built as done in the textbook, not as done by j flap.You can use jflap to help but you need to modify its output. Do not upload screenshots from jflap. Write your own tables.
