Exercise Set $3$:

In $1-6,$ if the language is regular, write either a regular expression or a

deterministic FSM for it$.$ If it is not regular, give a winning strategy for Player $2$ in

the "pumping lemma game".

Let $L$ be the language of all strings of the characters $\text{'}(\text{'}$ and $\text{'})\text{'}$ that are

balanced parentheses.

Let $L$ be the language of all strings of $a^{\text{'}}s$ and $b^{\text{'}}$ s with more $a^{\text{'}}$ s than $b^{\text{'}}s.$

Let $L$ be the language of all strings of a$\text{'}$s and b$\text{'}$s that have at least $2$ a$\text{'}$s and

at least $2b\text{'}$s$.$

Let $L$ be the language of all strings of a$\text{'}$s and b$\text{'}$s that end with $bb.$

Let $L$ be the language of all strings of a$\text{'}$s and b$\text{'}$s that consist of some number

of a$\text{'}$s followed by the same number of b$\text{'}$s$.$

Let $L$ be the language of all strings of a$\text{'}$s and b$\text{'}$s in which the sequence $ab$

occurs at least once.

Be able to state the pumping lemma for regular languages.