# Tag Info

1

HINT: Continue your table past $a^{15}$, maybe even to $a^{30}$, and pay careful attention to patterns. Or think about what it means for $n$ to be the least common multiple of $3$ and $5$. That’s not as much work as it may seem, but as a possibly quicker alternative you could start by looking at the problem of designing a DFA that accepts $a^n$ when $n$ is a ...

1

Hint: Suppose you have an automata for $\mathcal L_1$. Duplicate its set of states and send the letters between them in both directions.

1

In general, no. The shorthand $(a,b \to xyz)$ is often used, but means something else than what you're trying to do here. Recall that by $(a,b \to c)$ we mean that $a$ is the symbol that is read, $b$ is the symbol on top of the stack that is replaced with $c$. $(a,b \to xyz)$ is then usually taken to mean that \$(a,b \to x) \to (\varepsilon,\varepsilon \to y) ...

1

(The question is dated, but seeing a list of applications of more complex regular expressions may help someone, someday.) Some examples of possible applications of non-trivial regular expressions (using Kleene closure) are: A vending machine (that has no limit to how much money it accepts). This is interesting because of the variety of bills and coins ...

1

Hint: the complement of a regular language is regular. Can you prove that there's a/no way to construct a regular expression/finite state automaton that describes/accepts all strings in the English language?

Only top voted, non community-wiki answers of a minimum length are eligible