# Tag Info

## Hot answers tagged automata

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
Accepted

• 269k
1 vote

### When is a grammar ambiguous or When is a grammar not ambiguous?

That grammar as presented (with the addition of the production $A\to a$) is certainly ambiguous, regardless of what the site you copied it from says. Your work demonstrates that, and it can easily be ...
• 11k
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

### Is ε a part of alphabet or property of alphabet and NFA in FA

In the definition of $\Sigma_\epsilon$, $\epsilon$ is a letter (which must not belong to $\Sigma$). Elsewhere, $\epsilon$ is the empty word. To avoid confusion, you can use different symbols for the ...
• 269k

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