Tag Info

New answers tagged

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