Question

1. For the following grammars, write the leftmost derivation for the strings given with each. Next to each derivation step, write the number of the rule used. Do not combine steps.
2. grammar (6 rules), Σ = {0, 1}:

S -> A1B

A -> 0A | ε

B -> 0B | 1B | ε

strings (3): 1, 0011, 01010

3. grammar (6 rules), Σ = { +, x, a, (, ) }

E -> E + T | T

T -> T x F | F

F -> (E) | a

strings (3): a, a x a, (a) + a x a,

4. grammar (4 rules), Σ = {(, ), [, ]}:

S -> (S) | [S] | SS | ε

strings (3): ( ), [ ] ( ), ( [ ] )  

Answer 1

R1:S-> A1B
R2:A-> 0A
R3:A->ε
R4:B-> 0B
R5:B->1B
R6:B->ε

For string- 1
First we must use R1 because S is starting symbol
S -> A1B {leftmost variable is A therefore used R3}
=>1B { there is only one variable B used R6}
=>1 Answer
For String 0011
S -> A1B {R1}
=>0A1B {Leftmost variable is A used used R2}
=>00A1B {Leftmost variable is A used used R2}
=>001B {Leftmost variable is A used used R3}
=>0011B { there is only one variable B used R5}
=>0011 {there is only one variable B used R6}

S==>0011 Answer