# Tag Info

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.

0

Since the English language is finite and the regular languages are closed under complement..

0

I'll give you a strong hint: Think what happens when a language $L$ is concatenated with $\Sigma^*$.

0

This was first published by Hopcroft in 1969. See the elegant proof here.

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?

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 ...

0

Remember that $|vxy|\le p$. If $vxy$ includes the $\#$, obviously the $\#$ must be in $x$, so $v=a^k$ and $y=a^\ell$ for some $k$ and $\ell$ such that $1\le k+\ell\le p-1$. But then clearly $uxw\notin L$.

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 ...

0

A more general approach to solve minimisation of a DFA goes as follows: get rid of unreachable states. ($p \in Q$ is unreachable $\Leftrightarrow \forall s \in \Sigma^*: \delta^*(q_s, s) \neq p$) group all indistinguishable states and merge every group of mutually indistinguishable states to one new state. ($p$ and $q$ are indistinguishable if $\forall w ... 0 Hoda is absolutely correct. The way to see that regular languages are closed under intersection is as follows. Let$M(L), M(\Sigma^{*})$be the DFSMs to accept$L, \Sigma^{*}$respectively. We can assume DFSM WLOG, as if the machines are not deterministic, we can reduce them to deterministic machines. So then take an input string and run it on both ... 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) ...

Top 50 recent answers are included