New answers tagged

2 votes
Accepted

Is my DFA optimal?

Seems mimimal to me. You can actually prove that the DFA is minimal by applying the Myhill-Nerode theorem. Two states $p$ and $q$ can not be merged if they can be "distinguished" in the ...
  • 28.2k
2 votes

Is the reversal of a minimal DFA also minimal?

The "standard" example that shows that the NFA to DFA construction is exponential in size also works for reversal. The DFA for $\{0,1\}^*1\{0,1\}^n$, the $n+1$-st symbol from the right is $1$...
  • 28.2k
0 votes

Proof for Language: L1 ∪ L2 ⊆ L1L2

To prove $L_1 \cup L_2 \subseteq L_1L_2$ you prove that $\forall x. (x\in L_1 \cup L_2) \rightarrow(x\in L_1L_2)$   To prove that, you prove that $\forall x. (x\in L_1) \rightarrow(x\in L_1L_2)$ and $\...
  • 1,254
1 vote
Accepted

Minimal-length strings which are substrings of no string in a given CFL

Here is a possible approach. Enumerate lengths in increasing order (length 0, length 1, length). For each length, enumerate all strings in lexicographic order, as follows. Let's take length 4 as ...
  • 144k
5 votes

Non-regular language whose prefix language is regular but not the whole set of words

I'd take the language $(01)^n 0^m$ where m = 0 or 1, and 2n + m is a prime number. That is a string alternating between 0 and 1, and the length is a prime number. The prefix language is the regular ...
  • 25.9k
13 votes

Non-regular language whose prefix language is regular but not the whole set of words

Here's a quite simple example: the language $\{a^m b^{mn} : m, n \in \mathbb{N}\}$ is not regular, but its prefix language is recognised by the regular expression $\epsilon \mathop{|} a a^{*} b^{*}$.
  • 365
8 votes

Non-regular language whose prefix language is regular but not the whole set of words

Several simple examples The language $\{(01)^{n^2}: n\ge0\}$ is nonregular, but its prefix language is $(\epsilon+0)(10)^*(\epsilon + 1)$. The language $\{0^n1^m: 0\le n\le m\}$ is nonregular, but its ...
  • 35.3k
14 votes
Accepted

Non-regular language whose prefix language is regular but not the whole set of words

If there are no further rules, then there is a simple solution. In any existing example double all symbols in each string. That is, change the symbols $0$ and $1$ by the pairs $00$ and $11$. Formally ...
  • 28.2k
1 vote

Regularity of “middles” of words from regular language

Given a finite alphabet $\Sigma := \{a, b, \dots\}$, consider the so-called "tagged" alphabet $\Sigma' := \{a', b', \dots\}$. Consider the monoid morphisms $untag, killTag : \Sigma \cup \...
0 votes
Accepted

Does $L = \{a^n \ | \ n \geq 1, \ n \ \text{ is even or a square number}\}$ have infinite equivalence classes?

Change the description to "n is even or an odd square". For every r, let $k = 4r^2$. $a^k a^j$ is in the language if j is even, or if j is odd and k+j is a square. The smallest odd j is $(4r+...
  • 25.9k
0 votes

Show for every $CFL$ $L$ that's not $REG$ exists $L_1,L_2$ with $L_1$ is $REG$ and $L_1 \subseteq L_2$ and $L_2$ is not $REG$ and $L \subseteq L_2$

Since $L$ is not regular it is different than $\Sigma^*$. What would happen if you choose a word $u\notin L$ and consider $L\cup \{u\}$?
  • 7,534
0 votes

Show for every $CFL$ $L$ that's not $REG$ exists $L_1,L_2$ with $L_1$ is $REG$ and $L_1 \subseteq L_2$ and $L_2$ is not $REG$ and $L \subseteq L_2$

Your approach is not going to work. If $L=\{00\}$ (say) then you will not have $L \subseteq L_2$. Hint for a better approach: Could $L$ be $\{0,1\}^*$? Why or why not?
  • 144k
2 votes
Accepted

Suppose we have an empty alphabet Σ=∅, what are the possible languages of this alphabet?

Actually your list of properties already solves the problem. As $\varepsilon$ is an element of $\Sigma^*$ and we cannot have any longer word due to the lack of symbols, we have $\varnothing^*=\{\...
  • 28.2k
4 votes
Accepted

pumping lemma length restrictions clarification

First, for the sake of preciseness, note that the Lemma says that for every regular language $L$, there exists a constant $m\ge 1$, such that for every word $w\in L$... [what you wrote]. That is, the ...
  • 16.5k
3 votes

Is LR(1) closed under union?

A simple example is $$L_1 = \{a^i b^i c^j \mid i,j\ge 0\}$$ $$L_2 = \{a^i b^j c^j \mid i,j\ge 0\}$$ Clearly, both languages are $LR(1)$. (Indeed, they are $LL(1)$.) But their union is inherently ...
  • 11.4k
2 votes
Accepted

minimal DFA transition function clearification

$ \widehat{\delta(q, a)} = \hat{\delta}^{}(\hat{q}, a)$ The equality above is the definition of $\hat\delta$, given $\delta$. Let us paraphrase item 3. For each transition rule of $M$ of the form $$ ...
  • 35.3k
2 votes
Accepted

Prove or disprove: deterministic Turing machine equivalence Nondeterministic Turing machine such that word

Take a look at Micheal Sipser Introduction to the Theory of Computation 3rd edition pages 178 and 179. In short, the proof uses a three-tape turning machine $D$ (which is equivalent to an ordinary ...
  • 170
1 vote

How to recognize all halting states of a turing machine?

A turing machine is defined as a 7-tuple $M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle$. The set $F$ in the tuple is the set of final states or accepting states. So any other states other ...
  • 170
1 vote
Accepted

Is $\{a,b,c\}^* \setminus \{a^nb^mc^k \mid n \leq m \leq k\}$ context free?

No. $\{a^nb^mc^k\mid n>m>k\}$ is not the complement of $\{a^nb^mc^k\mid n\le m\le k\}$, for two reasons. (1) The negation of the logical statement "$P\land Q$" is not "$\lnot P\...
  • 28.2k
1 vote

Is $\{a,b,c\}^* \setminus \{a^nb^mc^k \mid n \leq m \leq k\}$ context free?

You ask: Isn't that also the complement of the language? Here that refers to $L' = \{a^n b^m c^k \mid n > m > k\}$ but I'm not sure what the language refers ...
  • 24.2k
1 vote
Accepted

Extended transition function in NFA

You can show that all states in the set on the left hand side are included in the set on the right hand side, and vice-versa. $s \in \delta_N^*(q, w)$ if and only if there is some path $\pi(q,s,w)$ ...
  • 24.2k

Top 50 recent answers are included