Here are some long-form exercises for you to work on to improve understanding and retention of course content. Short-form recall questions, designed to be part of your spaced-repetition learning regimen, can be found at the bottom of each page of course notes.
Here are some questions that might be found on an in-class paper-and-pencil exam.
Here are some problems that require some thinking, maybe a fair amount of research, and some actual work. They may involve writing little scripts, or making sketches. They aren’t exactly short-answer problems.
Some of the problems may refer to languages you have never heard of! If so, you can try solving the same problem with a language you are familiar with, or, better, look up the basics of the unfamiliar language so that you can take your best shot at the problem.
The first three problems are courtesy of Phil Dorin.
s = (x y z)* -- repeat xyz 0 or more times x y = y x -- switch them up all possible ways x z = z x y x = x y y z = z y z x = x z z y = y z x = "a" -- erase the variables y = "b" z = "c"
s = (l r)? -- start with left part and right part l = "a" l? x -- generate a's on the left, counting them with x's r = "b" r "d" | y -- generate equal nums of b's and d's leaving one y in the middle x "b" = "b" x -- move the x's to the right, in order to generate c's x y = y "c" -- when the x hits the y, make a c for it y = ε -- erase the y to finish it off
s = "a" x? "b" z "c" -- initial set up
x = "a" x "b" y -- if you generate an a, you must do b and c also
| x? "b"? y -- generate bc or c (keeping things increasing)
y "b" = "b" y -- move y's to the right
y z = z "c" -- when y hits the z, make a c
z = ε -- when the z is no longer needed, drop it
$\begin{array}{l} n \longrightarrow d^+ \; f? \; e? \\ f \longrightarrow \texttt{"."} \; d^+ \\ e \longrightarrow (\texttt{"E"} | \texttt{"e"})\; (\texttt{"+"} | \texttt{"–"})? \; d^+ \\ d \longrightarrow \texttt{"0"} .. \texttt{"9"} \\ \end{array}$
Give the $(V, \Sigma, R, S)$-definition of this grammar. (Note this means you will have to desugar the rules with|, ?, and +.)
$S → aab \mid aba \mid baa \mid aaSb \mid abSa \mid baSa \mid aSab \mid aSba \mid bSaa \mid SS$
Among the reasons that I have wanted to write is that, many years ago, my colleague, Ray Toal, whom you know, passed along a set of problem solutions that he received while studying at UCLA. They were for the 181 course—his instructor at the time was a fellow named Gabriel Robins, which probably tells you how long ago this was!—and they contained an error that I had always meant to report to you. (It’s been so long now that it has probably been corrected, but I’ll sleep a lot better once I’ve sent this off.) Specifically, the problem was to give a cfg that generated the set of all strings over alphabet $\{a,b\}$ with exactly twice as many $a$s as $b$s, which, I believe, was also a problem in an earlier edition of Hopcroft and Ullman. In any event, he gave the following solution, which he attributed to Lui:
S → SS S → aaSb S → abSa S → baSa S → aSab S → aSba S → bSaa S → aab S → aba S → baa
Now, I am going feel awfully much like an idiot if I am wrong about this, but... how does this grammar produce the string $aaabbbbaaaaa$ (that is, three $a$s, followed by four $b$s, followed by five $a$s)? I have managed to prove to myself that it simply can NOT produce this string, and I wonder if I should trouble you to look at it and let me know. (Technically, the grammar is also missing a rule for producing the empty string, which is also in the language, but that’s another matter.)
I do believe that a correct grammar is:
S → [empty string] S → SS S → aSaSb S → aSbSa S → bSaSa
I’ve also worked the problem from the other direction: I constructed a npda, converted it to a cfg, and simplified it (by removing useless symbols, etc.)—but the resulting grammar doesn’t look anything like the above ones, so this didn’t provide much new insight.
Prof. Greibach gave a nice reply, and as part of it managed to state almost nonchalantly the “obvious” proof (at least to her—in a single sentence!) of non membership of $aaabbbbaaaaa$:
It does indeed fail on the example you gave since the first rule applied could not be any of those starting S → a... or S → b... and S → SS cannot be used because the example is not the concatenation of 2 words in the language.
HELLO.EVEN,a,a,R,EVEN EVEN,b,b,R,ODD ODD,a,a,R,ODD ODD,b,b,R,EVEN EVEN,#,#,L,ACCEPT
lambda n: str(n)[1:-1]5 * 3 - 1 ** 3,
x = y * (2 + z). load y load 2 load z add mul store x
While this course does not focus too much on programming, keeping your programming skills sharp is always a good thing. Take the opportunity to learn new things as you do.