Exam 2 Review A

Problem X2rA.1.

Consider the following context-free grammar.

S

→

λ | a S b S | b S a S

Give a derivation of the string aabbab using this grammar.

Problem X2rA.2.

Give the derivation or syntax tree for yyx+yx+z using the below context-free grammar.

S	→	z | A + S
A	→	x | y A

Problem X2rA.3.

Consider the following context-free grammar.

S	→	T + S | T
T	→	F T | F
F	→	x | y | ( S )

Draw a syntax tree for the sentence x ( x + y ).

Problem X2rA.4.

Consider the following context-free grammar.

S	→	V V | V
V	→	( S ) | x | y | z

Each of the following sentences is either described by this grammar or not. If it is, give either a syntax tree with S at its root or a derivation from S. If it is not, simply say so.

a. x ( y )
b. x y z
c. x ( y z )

Problem X2rA.5.

Write a context-free grammar describing each of the following languages.

a.	the set of strings of a's and b's beginning and ending with the letter a
b.	the set of strings containing either only a's or only b's

Problem X2rA.6.

Write a context-free grammar describing each of the following languages.

a.	the set of strings containing only a's and b's consisting entirely of repetitions of the same letter, except the final letter, which must be different. Examples include aaaab, bbbbbba, and ab.
b.	the set of strings containing a's, b's, and c's where no a's appear after the first b

Problem X2rA.7.

Write a context-free grammar describing the set of strings containing only a's and b's with at least one a and at least one b.

Problem X2rA.8.

Write a context-free grammar that describes the strings of a's and b's containing exactly three a's. Examples in the language include aaa, abaab, and babbbabba, but not baaaab.

Problem X2rA.9.

Write a context-free grammar describing the language containing all strings of a's and b's for which the number of a's is even. Examples include aa, abbababa, and bbbb (since 0 is an even number).