PROBLEMS:

Let $\backslash$Sigma $=\{$a$,$ b$,$ c$\}$ for all problems.

$1.(5$ pts$)$ Let language L$1$ be the language where all strings contain the substring $$bab$.$ The strings

should NOT contain the symbol $$c$.$ Create a BNF grammar for L$1.$ Example: bab, abab, babb.

$2.(5$ pts$)$ Using your grammar, provide a derivation for the string u $=$ ababbab.

$3.(5$ pts$)$ Is your grammar regular? Explain why or why not.

$4.(5$ pts$)$ Is L$1$ regular? Explain why or why not.

$5.(5$ pts$)$ Let language L$2$ be the language where the strings must contain an $$a$$ after or before a $$c$.$

Strings may have no c$\text{'}$s at all. Examples of strings not in L$2$: abc, bcbaaba, cbbababb, empty string.

Examples of strings in L$2$: a$,$b$,$aa$,$bb$,$ab$,$ba$,$ca$,$ac$,$aca,caa,bac,bca. Create a BNF grammar for L$2.$

$6.(5$ pts$)$ Using your grammar, provide a derivation for the string u $=$ baccabb.