This assignment focuses on NFAs and regular expressions.
Let our alphabet contain only the symbols \(a\), \(b\). Consider the language L that consists of all strings consisting of “an \(a\) followed by an even number of \(b\)”, or “a \(b\) followed by any number of \(a\)s”, or finally any number of \(ab\)’s. Describe this via a regular expression.
In class we discussed how from a regular expression we can create an NFA for it. Do so for the regular expression from the previous problem. Make sure to not try to skip steps, follow the general construction.
In class we discussed how from a NFA we can create a DFA for the same language. Do this for the NFA from the previous problem.
Use the pumping lemma and other means to answer 1.46c.
Bonus/Extra-credit problem: 1.41