New answers tagged

0 votes
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, ...
user avatar
  • 23.4k
3 votes
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 ...
user avatar
  • 7,092
0 votes

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 ...
user avatar
  • 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 &...
user avatar
  • 34.1k
2 votes
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 &...
user avatar
  • 34.1k
5 votes

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 ...
user avatar
5 votes

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 ...
user avatar
  • 25.2k
11 votes
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\}$. ...
user avatar
  • 34.1k
0 votes
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$ ...
user avatar
6 votes

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. ...
user avatar
  • 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 ...
user avatar
  • 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\}^*\}$ ...
user avatar
  • 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 ...
user avatar
2 votes
Accepted

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

If $L$ is regular , then FirstHalves or $Half(L)$ is also regular. Algorithm: Design $DFA, M$ of language $L$ Find the reversal of $DFA$ ,$M$ , say $N.$ Traverse $M$ for one transition (for given $\...
user avatar
1 vote

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

I guess this question Prove half(L) is regular is the same. There are several ways to prove a language is regular: By building DFA, NFA, or Regular Expression (which is the case in your question). ...
user avatar
1 vote

CFL with regular substitution to make a regular language

Yes, you can. For instance: with language $L = \{a^nb^n \mid n\ge0\}$ and mapping $h(\epsilon)=\epsilon, h(a)=a, h(b)=a$ (which I think is what you meant to write), $h(L) = (aa)^*$. What is more: ...
user avatar
  • 4,676
3 votes
Accepted

Representing Determinstic Infinite Automata

As Yuval Filmus explains, every language can be recognized by an infinite-state DFA. So, it is not a concept that is of much interest in computability and automata theory. Of course you can represent ...
user avatar
  • 141k
1 vote

CFL with regular substitution to make a regular language

No,by your defined substitution CFLs remains CFLs. For example, $\{a^nb^n \mid n\ge0\} = \{\epsilon,ab, aabb, aaabbb,.......\}.$ After substitution by $h(a) = a$ and $h(b) =b$,$h(\epsilon) = \epsilon$ ...
user avatar
1 vote
Accepted

prove $A$ is context-free

This language is regular and this is an NFA that describes it: Please notice that the language has nothing to do with "counting" and it doesn't need any memory so you can simply realize it'...
user avatar
3 votes
Accepted

Prove that if C is a regular language, then the language $\{x x^R : x\in C\}$ is context-free

Recall that every finite state automaton can be changed into a rightlinear grammar which has productions like $X\to aY $ and $X\to \varepsilon$. Your language can be generated using the same technique,...
user avatar
  • 27.6k
0 votes
Accepted

prove that context free languages are closed under the $\circ$ operation

As you state the language $\{0^n 1 0^n\mid n\ge 0\}$ is context-free. (You do not need closure properties for this: $S\to 0S0\mid 1$ will do.) Now continue as follows. Consider instead the language $\{...
user avatar
  • 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 ...
user avatar
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$ ...
user avatar
3 votes
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 ...
user avatar
  • 27.6k

Top 50 recent answers are included