# Tag Info

Accepted

### Why does adding an $\epsilon$-transition to a DFA or NFA preserve the regularity of the language?

A language is regular if and only if there exists a NFA (equivalently a DFA) that recognizes it. Adding an $\varepsilon$-transition to a NFA (DFAs are special types of NFAs) still results in a NFA, ...
• 23.4k
Accepted

### DFA and NFA with 2 Substrings

Find an automaton for $L_1= \{uopv\mid u,v\in \Sigma^*\}$ and an automaton for $L_2 = \{upqv\mid u,v\in\Sigma^*\}$ (this should be easy enough). Then, you can compute the product automaton of the two ...
• 7,092

### in 2DPDA and 3DPDA:2 and 3 is the number of tapes or of stacks?

Your image comes from M.Li and P.M.B. Vitányi: Kolmogorov Complexity and its Applications, Chapter 4 in Handbook of Theoretical Computer Science, vol. A, J. van Leeuwen Editor. Both conjectures ...
• 27.6k
1 vote
Accepted

### variable repetitions in pumping lemma for context-free languages

It is certainly possible that some variables repeat in the subtree $T_3$, $T_4$ or $T_5$. There is nothing wrong with those situations, except that those situations are too relaxed for us to ensure &...
• 34.1k
Accepted

### substitution of same variable in context-free grammars

As you suspect probably, theorem 6.1 still holds even if $A$ and $B$ are the same variable. This can be seen by following the proof of the theorem, assuming $B$ is $A$. So, it is not correct to say &...
• 34.1k

### Why is { w | |w| mod 3 = #_a(w) mod 3 } a Regular Language?

So far every language that I saw containing modulo was a regular language. As John L. notes, that's a very good observation. Indeed, any language where the only constraint on words is that some ...
• 2,010

### Why is { w | |w| mod 3 = #_a(w) mod 3 } a Regular Language?

Lucky enough, your case is quite easy. The language is defined by the rule "total number of letters, modulo 3, equals total number of a's, modulo 3". This is equivalent to "number of ...
• 25.2k
Accepted

### Why is { w | |w| mod 3 = #_a(w) mod 3 } a Regular Language?

$\newcommand{\m}{\operatorname{\%}}$ Let $d(w)=(|w|-\#_a(w))\m3$, where $n\m 3$ is the remainder of dividing $n$ by $3$ as defined in almost every programming language. Note $L=\{ w\mid d(w)=0\}$. ...
• 34.1k
Accepted

### in 2DPDA and 3DPDA:2 and 3 is the number of tapes or of stacks?

$K{-}DPDA$ is equivalent to $2{-}DPDA$ for any $K \geq3.$That means for example $2{-}DPDA$ is capable of do the same work as $3{-}DPDA$ do, $2{-}DPDA$ is capable of do the same work as $4{-}DPDA$ ...
• 468

### Why is { w | |w| mod 3 = #_a(w) mod 3 } a Regular Language?

The following language is not regular $L = \{a^n b^m c^n \mid m = n \bmod 2\}$. To see that $L$ is not regular, suppose towards a contradiction that $L$ is regular and let $p$ be its pumping length. ...
• 23.4k
1 vote

### How to prove that $half(L)=\{x|xy\in L,|x|=|y|\}$ is Regular Language

The language $\mathrm{half}(L)=\{x\mid xy\in L,|x|=|y|\}$ can be quite complicated, compared to the original language $L$. I am afraid that there is no simple construction and we have to keep track of ...
• 27.6k
1 vote

### Prove or disprove that $\{xc o(x) :x \in A\}$ is context-free, where A is a regular language

Your operation is very general, and in its generality your conjecture is not true. For instance take for $o$ the identity, then we get the simple example $o(\{a,b\}^*) = \{wcw\mid w\in \{a,b\}^*\}$ ...
• 27.6k
1 vote

### If $L$ is regular then $\{x~|~\exists y ~~s.t~~ xyx^R \in L\}$ is regular

Start with an automaton for $L$, with states $Q$, initial state $q_0$, final states $F$, and transition function $\delta$. Construct a new automaton whose set of states is $Q \times 2^Q$. After ...
• 270k
Accepted

• 27.6k
1 vote

### How would I design a State Diagram (FSM) for a AC unit?

Your question's answer could be solved by Finite Automata with output that is Moore Machine or Mealy Machine. You have three cases: $Case:1$ When temperature is equal or more than $80°$ then output is ...
• 468
1 vote

### Checking my Pushdown automaton for $L = \{ 0^i1^j2^{i+j} | i \ge 0, j \ge 0, i+j > 0 \}$

First of all your language is DCFL so there exist at least one DPDA for your language but you made NPDA because at state $q_0$ ,$\delta(q_0,0,A)\neq\emptyset$ and $\delta(q_0,\epsilon,A)\neq\emptyset$ ...
• 468
Accepted

### Why 2- way DFA is equivalent to NFA (and thus DFA)?

The language $L=\{ (u\#,v\#) \mid |u|=|2v|\}$ from your question is actually a two-dimensional language, that is a relation between two strings, each written on their own input tape. In that way the ...
• 27.6k

Top 50 recent answers are included