8
votes
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
7
votes
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
6
votes
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$...
5
votes
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
5
votes
Decidability of whether for a given $G$, $L(G)=\Sigma^+$? (or $L(G)=L$ where $L$ is fixed beforehand
It is decidable whether $\epsilon \in L(G)$. Given a context-free grammar $G$, you can construct a new context-free grammar $G'$ such that $L(G')=L(G) \cap \Sigma^+$. If $L(G')=\Sigma^+$ and $\...
D.W.♦
- 164k
4
votes
Applications of ω-automaton in engineering
Sure. They are used in model checking. Specifically, if we want to check liveness properties of systems, then typically we use $\omega$-automata (e.g., Büchi automata) to formalize the property we ...
D.W.♦
- 164k
4
votes
Accepted
Difference between product automaton vs. NFA with epsilon transitions
Both constructions work. The advantages of using NFAs is that they allow easier constructions, especially for languages that can be naturally specified using existential quantifiers. So if we only ...
- 4,735
4
votes
Accepted
A context-sensite grammar for the language of sequences of two different types of parentheses with possible intersections?
Basically, the idea is that $($ and $)$ can commute with $[$ and $]$, but $($ cannot commute with $)$ – and same for $[$ and $]$.
An essentially noncontracting grammar would be:
$S \to \varepsilon \...
- 16k
4
votes
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
4
votes
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
4
votes
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
3
votes
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
3
votes
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
3
votes
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
3
votes
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
3
votes
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
3
votes
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
3
votes
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
3
votes
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 ...
D.W.♦
- 164k
3
votes
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
3
votes
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
3
votes
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
2
votes
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
2
votes
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
2
votes
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
2
votes
Is the set of all DFAs countable?
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
2
votes
Proving a language is not regular using Pumping Lemma
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 ...
- 306
2
votes
Accepted
NFA for the language that accepts binary strings ending with 00
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^*...
- 4,735
Only top scored, non community-wiki answers of a minimum length are eligible