12
votes
Conjecture: a half of a pairing context-free language must be a regular language
No, this conjecture is not true.
Consider $A=\{0^n1^n \mid n\geqslant0 \}$ and $B=\{1^{2n}\mid n\geqslant0\}$.
We have $\{|a| : a\in A\}=\{|b| : b\in B\}=\{2n\mid n\geqslant0\}$ and $A\bowtie B = \{ 0^...
- 33k
8
votes
Accepted
Determining if an NFA accepts an infinite language in polynomial time
Since $\epsilon$-transitions can be removed in polynomial time, let us assume for simplicity that the NFA does not contain any $\epsilon$-transitions (though the argument can be modified to ...
- 269k
6
votes
Determining if an NFA accepts an infinite language in polynomial time
An NFA (with $\epsilon$-moves or not) can be viewed naturally as a directed multi-graph. We will use "state" and "node" interchangeably.
Whether an NFA accepts an infinite ...
- 33k
4
votes
Proving Equivalence of Two Regular Expressions
If you wanted to prove this extra formally, you could try to prove this in a proof assistant, such as Lean (or Coq or Agda or ...). Here's how you can state that problem using Lean's ...
- 143
4
votes
If $L$ is regular then so is $\{y \mid \exists x \, xyx \in L\}$
Take a DFA $(Q,\Sigma,\delta,q_0,F)$ accepting $\mathcal{L}$. We can associate each word $x \in \Sigma^*$ with a function $\delta_x\colon Q \to Q$ given by $\delta_x(q) = \delta(q,x)$. In other words, ...
- 269k
4
votes
Is the set of languages satisfying the pumping lemma closed under concatenation?
Suppose that $L_1$ satisfies the pumping lemma: there exists $p_1$ such that every word $w \in L_1$ of length at least $p$ can be decomposed as $w = xyz$, where $|xy| \leq p_1$, $y \neq \epsilon$, and ...
- 269k
3
votes
Accepted
How to convert AFA to ε-NFA / NFA / DFA?
The construction yields a nondeterministic NFA $A'$ that is equivalent to the original alternating AFA $A$.
The states of the new automaton are sets of states of $A$, just as in the classic ...
- 27.2k
3
votes
If $L$ is regular then so is $\{y \mid \exists x \, xyx \in L\}$
Idea: Suppose we have an NFA $(Q, \Sigma, \Delta, I, F)$ for $\mathcal{L}$. To build an NFA for $\text{SW}(\mathcal{L})$, our plan is to make a separate copy of the states of the NFA for each ...
- 5,144
2
votes
Proving Equivalence of Two Regular Expressions
If you generate a minimal DFA from a regular expression, then you can label each state uniquely with the lexically smallest string that reaches the state.
This makes it very easy to check for ...
- 464
2
votes
Accepted
Converting Regular Expression to Finite Automata
The construction that you show from the book of Sipser is known as Thompson’s construction, building a nondeterministic automaton with $\varepsilon$-transitions. Those empty transitions can be removed ...
- 27.2k
2
votes
Accepted
Prove irregularity of a language using closure properties
Suppose that $L$ is regular. Since regular languages are closed under intersection, then
$$
K = L \cap a^*c^* = \{a^{j+1}c^j \mid j \geqslant 0 \}
$$
would be regular and the left quotient of $K$ by $...
- 5,925
2
votes
Accepted
What exactly is pumping length in pumping lemma?
The pumping length $n$ must be assumed to be arbitrary - you can't fix it to be a particular value. The pumping lemma is used to prove that a given language is nonregular, and it is a proof by ...
- 1,005
1
vote
prove that if L is context-free then L' = {w2#w1 | w1#w2∈L} is context-free
There is a unique path in the derivation tree that leads from the axiom $S$ to the terminal symbol $\#$. An idea would be to turn this tree upside down along that path.
This solution follows the ...
- 27.2k
1
vote
If $L$ is regular then so is $\{y \mid \exists x \, xyx \in L\}$
If $L$ is a language of $A^*$ and $u, v$ are words, let
$$
u^{-1}Lv^{-1} = \{ x \in A^* \mid uxv \in L \}
$$
It is a well-known fact that if $L$ is regular, then every language $u^{-1}Lv^{-1}$ is ...
- 5,925
1
vote
Prove that the language of regular expressions is not regular
Yes, this will work: if you may assume that the language of matching brackets is non-regular, it suffices to know that whenever a language is regular, erasing all occurrences of a particular character ...
- 4,611
1
vote
What exactly is pumping length in pumping lemma?
The "Pumping Length" "n" exists because you can write a finite automata that classifies all strings up to a fixed, finite length in any way it wants to.
Your finite automata can ...
- 785
1
vote
What exactly is pumping length in pumping lemma?
When using the pumping lemma, you do assume such $p$ exists, assuming that the language is regular. This $p$, no matter what it is, should exists since it is the number of states for the DFA of the ...
- 1,257
1
vote
Accepted
Irregularity of $\{b^ma^n: (m,n)=1\}$ using Nerode
Let $P$ be the set of all primes. Show that the words $\{b^p : p \in P\}$ belong to different equivalence classes.
- 269k
1
vote
Construct a regular expression for the set of strings over {a, b} that contain an odd number of a's and at most four b's
Here is how to construct a regular expression for the set of strings over $\{a,b\}$ which contain an even number of $a$'s and at most one $b$.
Strings that contain no $b$ are of the form $a^n$, where $...
- 269k
Only top scored, non community-wiki answers of a minimum length are eligible