Hw4 - sghsdfgsdfgsdfgsdfgadfga asefa sef asefa dsrga sdfa sdf PDF

Preview

Summary

sghsdfgsdfgsdfgsdfgadfga asefa sef asefa dsrga sdfa sdf...

Description

CS 138 Homework 4 Due Monday, May 4 11:59 PM • Each autograded problem is worth 2 points (no partial credit). • Other problems (i.e. pen-and-paper problems) are worth 4 points each (unless stated otherwise in the problem description). • Unless stated otherwise on a problem, if you write I don’t know as an answer to any pen-and-paper problems (or their parts), you get 25% of the points for that problem/part. • Submit the solutions to the CFG problems as .cfg files with the problem number (e.g. 1.cfg) separately to the autograder. Note about the CFG construction problems: Mentor allows you to have a variable with multiple letters, so Expr is a valid variable. So is Sa. This leads to a gotcha: When writing a production rule such as S → Sa in Mentor, you need to put a space between S and aand you should have S -> S a. In all of the problems below, the start variable is S unless stated otherwise.

Problem 1 For this problem, you are going to describe a fragment of the C language. Specifically, you are going to describe sequences of assignment statements involving the variable x, the constant 1, and addition. The set of terminals for this problem are { x, 1, +, ;, = }. A valid assignment statement has a variable on the left-hand side and an expression on the right-hand side, and it ends with a semicolon. For example, x=x+1; and x=1; are valid statements. The following are not valid assignment statements: x+1=x; (left-hand side is not a variable), x=; (right-hand side is missing), x=x+1 (no semicolon at the end). The language in this problem contains a sequence of assignments. So, for example, the following are in the language: • ε – 0 statements • x=x+1; – 1 statement • x=x;x=x+1; – 2 statements Submit your solution as 1.cfg to the autograder.

Problem 2 Show that the following language is context-free by providing a CFG. Submit your solution as 2.cfg to the autograder. IMBALANCE = { ax by cz | x 6= y ∨ x < z } . 1

Problem 3 Show that the following language is context-free by providing a CFG. Submit your solution as 3.cfg to the autograder. ACAB = { an cm ap bq | n + m = p + q } .

Problem 4 Show that the following grammar is ambiguous by finding either two leftmost derivations or two parse trees for a string. S → SS | aSb | ε

Problem 5 Prove that the grammar G you submitted for problem 2 recognizes the language IMBALANCE . That is, S ⇒∗ w if and only if w ∈ IMBALANCE . Here, S is the start variable of your grammar. The proof for this may be involved, so it would be easier if you split the language into different sub-languages and have distinct parts of your grammar handle different cases.

2...