# Tag Info

Accepted

### How to show L is non-regular without pumping lemma?

Well, you can't show that it is not regular, because it is regular. Indeed, $L = (ab)^*\setminus \{(ab)^6\}$, and $(ab)^*$ is regular (concatenation + kleene star), and $\{(ab)^6\}$ is regular (...
• 16k

### Are there infinite state machines, and how do their computational power relate to turing machines?

Turing machines aren't defined this way simply because automata with an infinite number of states aren't effective. The definition of effective procedures tries to capture our intuitive understanding ...
• 1,549
Accepted

### Subset Relations Between CFGs and Their Languages

Let $G$ and $H$ be your two context-free grammars, respectively. If the set of all rules in $G$ is a subset of the set of all rules in $H$, then all derivations possible in $G$ are also possible in $H$...
Accepted

### Repeated rules with more than three symbols for conversion to Chomskys Normal Form

Yes, if the same strings are generated the productions can be shared. The "standard" conversion does not consider such "coincidences". Note that your final result does not yet ...
• 30.9k

• 16k
Accepted

### Can code using GOTO be converted GOTO-less algorithmically?

Yes, it's possible, but the construction is probably a lot less satisfying than you imagine it being ;) Each program can be expressed using only goto <line> ...
• 1,549
Accepted

### $L'=\left \{w : w\cdot Drop_a(w)\in L \right \}$ is a regular language

Note that a word $w$ is in $L'$ iff there exist states $q\in Q, q_f\in F$ such that $q_0 \xrightarrow{w} q$ and $q \xrightarrow{drop(w)} q_{f}$, where the latter runs are runs in $A$. The first run is ...
• 4,735
Accepted

### $L'=\left \{ z^Rx : xyz\in L \right \}$ is regular

Let $A = (\Sigma, Q, q_0, \delta, F)$ be a DFA that recognizes $L$. For states $p, q\in Q$, let $A_{p, q}$ denote the DFA obtained from $A$ by letting $p$ be the initial state and $q$ be the only ...
• 4,735

### Shortest regular expression possible

To solve this question, you should not blindly apply some algorithm. Instead, start by understanding what the given automaton does. When you do this, you will see that the automaton is needlessly ...
• 3,213

### Question about ALL-NFA in PSPACE

Note that the procedure decides the complement of $ALL_{NFA}$, which is sufficient as $PSPACE = NPSPACE$. The procedure checks whether the NFA $M$ rejects some input. The idea is simple, we actually ...
• 4,735
Accepted

### Shortest regular expression possible

Frame it as the least fixed point solution to the following system in Kleene algebra:  A ≥ 1 + a B + b C,\quad B ≥ 1 + a D + b E,\quad C ≥ 1 + a D + b D,\\ D ≥ a B + b C,\quad E ≥ a C + b B,\quad A. ...
• 349

### Is matching pairs sufficient?

I assume that the Turing machine $M$ is allowed to be nondeterministic. In that case we need three positions. Consider the possibility that $M$ on a certain configuration may move either left or right....
• 30.9k

### NFA for a regular expression without $\epsilon$-transitions

You can convert the regular expression into an automaton using the Glushkov's construction. The resulting automaton is non-deterministic and does not contain any $\varepsilon$-transition. Its number ...
• 16k

### Do multi-acceptance/multi-language automata exist in literature?

There have been studies on something called colored finite automata, which seem very close to your definition. Other colored models, e.g. regular expressions, also exist. I haven't work on this ...
• 31
Accepted

### How to formally prove that any regular expression can be written as a finite combination of base cases and operations?

What you have there is a recursive definition. Every regular expression is generated by a finite number of applications of rules 1.-6., so you can simply do mathematical induction over the number of ...
• 1,549
Accepted

### What is the name of a DFA where all long enough words are synchronizing words?

I don't know whether it has a name, but you can test in polynomial time whether a DFA has this property or not, as it is a 2-safety property. Specifically, a DFA fails to have this property iff there ...
• 164k
Accepted

### Question about a grammar who generates $(0+1)^*$

We can prove this using mathematical induction. For base case, it is easy to see that $S$ can generate $\varepsilon, 0, 1, 00, 11, 01, 10$. Now we assume $S$ can generate any binary string on $0$s and ...
• 1,934
Accepted

### Lower bound states for NFAs: seeking examples and methods

Following your edit: NFAs are closed under reversal in $O(1)$. Indeed, take an NFA with $n$ states, then you can obtain an NFA for the reverse by reversing the transitions and swapping the accepting ...
• 17.4k
Accepted

### Myhill-Nerode sentence and the relation $R_L$

Note that $u, v$ and $w$ can contain any letter. Therefore, $L$ is the language of all words that contain some letter at least twice. In particular, a word that contains some letter 3 times is in $L$. ...
• 4,735

### How does a minimal DFA ensure minimal computational cost?

As Yuval commented, I also think you're taking Wikipedia too literally. The way I interpreted that sentence is as follows. Decision procedures about deterministic automata are easier compared to ...
• 4,735

### Why are non-deterministic Buchi automata factorially succinct when compared to deterministic Rabin Automata?

Usually, when defining the size of a Rabin automaton, we take into consideration the automaton's index (the number of Rabin pairs) and not only the number of states. What you asked for is well-known, ...
• 4,735

### Proving that $(A \cup B)^* = A^*(BA^*)^*$

As already stated in the comments, it is easy to see that $A^*(BA^*)^* \subseteq (A\cup B)^*$ as every word $x$ in $A^*(BA^*)^*$ can be written as a concatenation of words that are either in $A$ or ...
• 4,735

There are several ways to prove this. Here is a formal one: You can encode the set of DFAs over $\Sigma$ as words over the constant alphabet $\Sigma' = \{0, 1, \#\}$. This can be done as follows. Let $... • 4,735 2 votes Accepted ### How to check whether a given language is decidable when the definition contains some predetermined machine The machine$M_1$is not a predetermined machine, but we rather find that$M_1$is within the scope of an existential quantor. As you have observed, for all$w$and$M$there is some$M_1$such that$...
• 3,213
In the case of the pumping lemma, it is not good for intuition or practice to consider specific strings, such as $abba$. The statement of the pumping lemma says that if a language $L$ is regular, then ...
The first answer is incorrect. The automaton does not accept, for example, the input word $0100$. In fact, the first automaton misses at least all words in the language that are not of the form \$1^*0^*...