## Question

Acceptable file formats are: ASCII text (like those prepared with NOTEPAD), MS Word, and PDF. You

should clear with me in advance any other formats.

When you prepare your homework, do not try to make it fancy. The focus is not on the form, but on the content. "Typewriter graphics" are fine. You may scan handwritten diagrams or figures as long as they are readable, however, scanned handwritten text is not acceptable. If I cannot read something, I will assume that it is wrong.

1. Using the grammar show a parse tree and a leftmost derivation for the following statement (make sure you do not omit parentheses in your derivation):

C = (A+B)*(C+A)*(C+B)

2. Consider the following grammar(S is the start symbol; 0 and 1 are terminal symbols; A and B are nonterminals)

S -> 0B | 1A

A -> 0B

B -> 1A | 1

Which of the following sentences are in the language generated by the grammar? Show derivations. If a sentence cannot be generated by the grammar, explain why.

a) 01010100

b) 01010101

c) 10101010

d) 10010011

3. For the following grammar and the right sentential form F * (id + id) draw a parse tree and show all phrases, simple phrases, and the handle (E, T, and F are nonterminal symbols; id is a terminal symbol). Explain.

E -> E + T | T

T -> T * F | F

F -> (E) | id

4. Transform the following left recursive EBNF grammar into an equivalent non-left recursive grammar (S and A are nonterminal symbols; S is the start symbol; a and b are terminal symbols):

S -> aSb | bAS

A -> AaA | bAA | AAa | bAb

## Solution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

1. Using the grammar in Example 3.4 (page 125) show a parse tree and a leftmost derivation for the following statement (make sure you do not omit parentheses in your derivation):C = (A+B)*(C+A)*(C+B)

<assign> => <id> = <expr>

=> C = <expr>

=> C = <term>

=> C = <term> * <factor>

=> C = <term> * <factor> * <factor>

=> C = <factor> * <factor> * <factor>

=> C = (<expr>) * <factor> * <factor>

=> C = (<expr> + <term>) * <factor> * <factor>

=> C = (<term> + <term>) * <factor> * <factor>

=> C = (<factor> + <term>) * <factor> * <factor>

=> C = (<id> + <term>) * <factor> * <factor>

=> C = (A + <term>) * <factor> * <factor>

=> C = (A + <factor>) * <factor> * <factor>

=> C = (A + <id>) * <factor> * <factor>

=> C = (A + B) * <factor> * <factor>

=> C = (A + B) * (<expr>) * <factor>

=> C = (A + B) * (<expr> + <term>) * <factor>

=> C = (A + B) * (<term> + <term>) * <factor>

=> C = (A + B) * (<factor> + <term>) * <factor>

=> C = (A + B) * (<id> + <term>) * <factor>

=> C = (A + B) * (C + <factor>) * <factor>

=> C = (A + B) * (C + <id>) * <factor>

=> C = (A + B) * (C + A) * <factor>...

By purchasing this solution you'll be able to access the following files:

Solution.docx.