Problems and topics listed here are for open discussion and practice. Feel free to work with a partner or ask the instructor questions. Towards the end of the lab period we may review some but not necessarily all answers. You are welcome to discuss solutions and strategies to these problems openly with classmates and the instructor outside of lab/class, on Piazza, and office hours.
Reading for next week
Check the reading for next week and read through chapters 2.1-2.3
Sample Problems
You do not need to submit any solutions to these problems. This work will not be graded.
- Show via the pumping lemma that $L= \{ ab^nc^n, n\geq 0 \}$ is not regular. You will need to consider at least two cases for the form of $y$ in your proof.
- Consider the language $C=\text{op}(A,B)$ where op is some operation that is closed under regular languages. Suppose we know the following about $A$ and $C$. What, if anything, can we conclude about $B$?
- $A$ is regular and $C$ is regular.
- $A$ is regular and $C$ is not regular.
- $A$ is not regular and $C$ is regular.
- $A$ is not regular and $C$ is not regular.
- Consider the language $C=\text{op}(A,B)$ where op is some operation that is closed under regular languages. Suppose we know the following about $A$ and $B$. What, if anything, can we conclude about $C$?
- $A$ is regular and $B$ is regular.
- $A$ is regular and $B$ is not regular.
- $A$ is not regular and $B$ is regular.
- $A$ is not regular and $B$ is not regular.
- Many programming languages use braces {} , brackets [], and parentheses () to group functions, blocks, classes, etc. These braces, brackets, and parentheses must be balanced in the
sense that you cannot have a closing brace without a previous matching opening brace, all
open braces must eventually have a matching closing brace, and you cannot close a brace with an unmatched open brace "inside."" The following examples are legal: ()(), (({})[{}]{{}}),
and {}[()], but [(]), ((, and (} are not. Design a context free grammar that generates balanced
statements containing braces, brackets, and parentheses.
- Give a context-free grammar generating the set of strings over $\Sigma = \{a, b\}$
containing more $a$s than $b$s.
Give an informal English-language description of a PDA for this language.
- Give a context-free grammar generating the language:
$$ \{w\#x \ | \ w^R \text{ is a substring of } x, \text{ where } w, x \in \{a, b\}^* \} \subseteq \{ a, b, \#\}^* $$
Give an informal English-language description of a PDA for this language.