CS200 Spring 2016 HW1

Procedure

Create a plain text file called hw1.txt, which looks like this:

    Q1:
    answer for question #1

    Q2:
    answer for question #2
    …

Turn it in via web checkin, or like this:

    ~cs200/bin/checkin HW1 hw1.txt

Do not turn in a paper copy.

Questions

Q1: Write a regular expression defining dogs, using the following grammar:

dog = cat | dog cat | dog bear
cat = a | b | c
bear = 2 | 3 | 5 | 7

Given the following two grammars for matching brackets:

Grammar 1: Alpha = [ ] | [ Alpha ] | Alpha Alpha
Grammar 2: Beta = [ ] | [ Beta ]

Q2: Show a derivation of [ ] [ ] [ ] using Grammar 1, starting with Alpha
Q3: Show a derivation of [ [ [ ] ] ] using Grammar 2, starting with Beta
Q4: Is [ ] [ ] produced by Grammar 2? (Y/N)
Q5: Is [ [ ] ] produced by Grammar 1? (Y/N)
Q6: Is [ [ ] ] produced by Grammar 2? (Y/N)

Complete the following table, keeping the operands in the same order. Use Java operator precedence.

Prefix expression	Infix expression	Postfix expression
/ - a b c	(a-b) / c	a b - c /
Q7	Q8	a b c d + - *
* % a b + c d	Q9	Q10
Q11	a + b * c	Q12
Q13	true \|\| true && false	true true false && \|\|
Q14	a>=b \|\| c<d	Q15