New answers tagged formal-languages
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 ...
D.W.♦
- 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 \...
- 11
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?
D.W.♦
- 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