2
The formulation
every substring 000 appears after every 1
is extremely ambiguous. However, given the proposed solution, here is how we are supposed to interpret it. Let $w$ and $x = x_0 \ldots x_{m-1}$ be words. We say that $x$ occurs in $w$ at position $i$ if $$w_i w_{i+1} \ldots w_{i+m-1} = x_0 x_1 \ldots x_{m-1}.$$
The language in question consists of ...
3
The number $504$ has $4\cdot3\cdot2=24$ divisors:
$$1,
2,
3,
4,
6,
7,
8,
9,
12,
14,
18,
21,
24,
28,
36,
42,
56,
63,
72,
84,
126,
168,
252,
504$$
Out of these, $20$ are at least $6$:
$$
6,
7,
8,
9,
12,
14,
18,
21,
24,
28,
36,
42,
56,
63,
72,
84,
126,
168,
252,
504$$
For an integer $n$, $\operatorname{gcd}(n,504) \geq ...
2
The language is in RE: simply generate all inputs $x$ with $|x|\le 10000$ (they are finitely many), and simulate $T$ on all inputs in parallel. Whenever one simulation halts, accept.
The language is not in co-RE, as otherwise it would be decidable and we could solve the Halting problem.
Indeed, to decide whether a Turing machine $T$ halts on empty input, we ...
1
This language can be described as 'zero or more zeroes followed by zero ore more ones, where if the number of zeroes is even, so are the number of ones, and vice versa'.
So you just need to keep track of the parity of both the zeroes and ones, and if they match, accept.
1
If we take $L = \{a^n \mid n \in \mathbb{N}\}$, then $L' = \{a^{2n} \mid n \in \mathbb{N}\}$, which is a perfectly fine regular language. Or even more trival, we could observe that $\emptyset' = \emptyset$.
As such, it does not hold that $L'$ is never regular for a regular language $L$. This means that answering the question will involve constructing a ...
1
Yes. You can obtain a PDA with only one state by "encodng" the state of your PDA into the stack of the new PDA. See this document.
1
Any word can be written as a concatenation of runs. For example,
$$ aaabbabaccbbbc = a^3b^2a^1b^1a^1c^2b^3c^1. $$
Each run is a positive power of a symbol, and the constraint is that two adjacent runs are powers of different symbols. Each word can be decomposed into runs in a unique way.
The regular expression $(a+b)^*c^*(a+b)^*$ captures all words with at ...
Only top voted, non community-wiki answers of a minimum length are eligible
