//Programming Languages

//Please answer the following

3. a. Write a grammar for the language consisting of strings built only of the letters a and b. The

strings may have any number of these letters, but the letter combinations bab must be in each

string somewhere, and each string must start with a aba. For example, the strings ababab,

abaaaaaabab, and ababbbabbbab are in the language, while a, aabb, baaa, and aba are not.

b. Draw the parse tree for string qhzyhz according the following grammar in BNF (start symbol

is ):

::= q | q

::= u

::= z | y

::= h

c. Describe, in English, the language defined by the following grammar in BNF (start symbol is

):

::= |

::= a | c | d

::= ba |

::= ab |

d. Consider the following grammar in BNF (start symbol is ):

::= a | | b

::= c | c

::= b | b

Which of the following sentences are in the language generated by this grammar? Explain your

answer for each possible sentence.

abc

cccabbb

aabbbb

abccc