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^...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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, ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 $...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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.
user avatar
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 $...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible