Some grammar formalisms exercises

Problem 1. Here is a grammar over the alphabet $\Sigma = {a,b}$:

$$\begin{align*} S &\to aS \\ S &\to b \end{align*}$$

See if you can answer these questions:

• Is it regular?
• Is $aab$ in its language? Is $aba$ in its language? What about $aaaaaab$?
• Can you describe in words what kind of strings are in its language?
• Can you write a regular expression that matches precisely the strings in its language?
• Can you draw a DFA that accepts the strings in this language?

Problem 2. Here is a grammar over the alphabet $\Sigma = {a,b,c}$:

$$\begin{align*} S &\to aS \\ S &\to A \\ A &\to bB \\ B &\to cB \\ B &\to \epsilon \end{align*}$$

• Is it regular?
• Is $aaabcccc$ in this language? Is $abc$? What about $bbcc$ and $aacc$?
• Can you describe in words exactly which strings are generated by the grammar?
• Can you make a regular expression and a DFA that match the strings in this language?

Problem 3. Here is a grammar over the alphabet $\Sigma = {a,b}$:

$$\begin{align*} S &\to A \\ S &\to B \\ A &\to aA \\ B &\to bB \\ A &\to \epsilon \\ B &\to \epsilon \end{align*}$$

• Is it regular?
• Are $aaa$, $bbb$, $aba$, $aaaaab$ in this language?
• Can you find a pattern and describe which strings are in this language?
• Can you make a regular expression and a DFA that match the strings in this language?

Problem 4. Here is a grammar over the alphabet $\Sigma = {a,b,c}$:

$$\begin{align*} S &\to aSc \\ S &\to A \\ A &\to bAc \\ A &\to \epsilon \end{align*}$$

• Is it regular? If not, what kind of grammar is it?
• Are $abc$, $abcc$, $aabbcc$, $abbccc$ in this language?
• Can you find a pattern and describe exactly which strings are generated by this grammar?

Problem 5. Here is a grammar over the alphabet $\Sigma = {a,b}$:

$$\begin{align*} S &\to aSA \\ S &\to b \\ A &\to bA \\ A &\to \epsilon \end{align*}$$

This grammar is not regular because one of the rules is a type of rule that is not allowed for regular grammars. (Which rule?)

However, the language generated by this grammar, that is, all of the possible strings produced by these rules, is actually regular! That means it's possible to write a regular grammar (with different rules) that generates the same language, even though its rules are different.

• Can you describe the language in words? Which strings can be produced by these rules?
• Can you write a regular expression that also accepts those strings?
• Can you figure out a regular grammar for the same language?

Problem 6. Here are some regular expressions. Can you figure out a DFA that accepts each one?

• a*b*
• a*b*c*
• a+b*
• (a|b)
• (a*|b*)
• a(b|c)+a
• (aaa|bbb)?
• (ab)*(abc)?

Problem 7. Here is a DFA:

• Does it accept $\epsilon$? How about $a$, $ab$, $abbbb$, $ba$, $baa$, $bab$?
• Does it accept the string $aabbababababababaabababababbbbbbababababa$? (This string is long, but it does not actually take a long time to figure out the answer!)
• Can you write a regular expression that describes which strings this automaton accepts?