3
Below a nondeterministic automaton for the language of all strings where the one-but-last letter is an $a$. If we make it determinsitic using the standard construction half of the states will be unreachable.
You ask, why does this happen? Look at the initial state $0$ of the original automaton. It has a loop for both $a$ and $b$. That means that in the ...
3
Suppose that the input alphabet is $\{0,1\}$, and consider the language $L_1 = 0^*$. We can easily construct a Turing machine $T_1$ such that $S_{T_1}(I) = |I|+1$. On the other hand, $S_{T_2}(I_c) \geq |I_c|+1$. Since $|I_c|=|I_1|+1+|I_2|$, we get
$$
S_{T_2}(I_c) \geq |I_1|+1+|I_2|+1 = S_{T_1}(I_1) + S_{T_1}(I_2).
$$
2
I'll try to answer your remaining question: what are analog and digital in computer science?
The trouble is that these terms aren't from computer science. They are from the field called "signal processing". When someone says "analog computer", they simply mean that the computer is designed on principles of analog signal processing and ...
2
If the construction method supports "negative" regular expression operators, such as set intersection or set difference, it's likely that the method will produce useless states. For example, Brzozowski's method, when given the expression $\left(a \cup b\right)^* \setminus \left( a \left( a \cup b\right)^* \right)$, will likely produce something ...
2
If you run $M$ on the $i$-th string then it might never halt, so your algorithm will be stuck. The idea is that if $M$ does halt on the $i$-th string, say after $j$ steps, then we will see it once we get to the $\max(i,j)$-th string.
2
This is not an answer, but way too long to be a comment. I just wanted to cite Robert I. Soare's Recursively Enumerable Sets and Degrees, Chapter V: Simple Sets and Post's Problem.
1: Immune Sets, Simple Sets, and Post's Construction
The only r.e. degrees constructed so far are $\textbf{0}$ and
$\textbf{0}'$. Post's Problem was to construct other r.e. ...
1
What you call a "liar" program is typically called a diagonalization argument, since it somehow resembles Cantor's diagonalization argument.
Usually what we mean by that is that if we try to enumerate all elements with a certain property, then we can point out, by construction, an element that is necessarily "incorrect", and we do so by ...
1
Let me expand on the first sentence of Yuval Filmus' answer:
We can associate a language to a Turing machine in several ways.
Yuval mentions two: acceptance (which characterizes $\mathsf{R}$) and recognition (which characterizes $\mathsf{RE}$). There are others, however. Most obviously, we could consider "co-recognition" - say that a Turing ...
1
We can associate a language to a Turing machine in several ways.
If the Turing machine halts on all inputs, then the language accepted by the Turing machine consists of all words which cause the Turing machine to halt in an accepting state. The class $\mathsf{R}$ consists of all languages which are accepted by some Turing machine.
For an arbitrary Turing ...
1
Before we had electric or electronic calculators, there were mechanical calculators. These worked with whole numbers, so they were digital, but they were powered by hand (typically by turning a crank) not by electricity.
On the other hand, in the period 1900 to 1960 there were a variety of analogue computers that were powered by electricity. Even though ...
1
There is a distinction between continuous phenomena and discrete. It's the former than is called analog in computer science and the latter, digital.
After all, the digits 0 and 1 are discrete.
Whilst [0,1], the interval between 0 and 1 is continuous and so analog. (I don't know if you are familiar with the notation [a,b]. It simply means all numbers between ...
1
Yuval's answer describes the main component. For the sake of completeness I'll precise a couple of details.
First, $L(M_1) \neq L(M_2)$ means that there is a string that is accepted by one of the automaton but not the other. Let's "build" an automaton $M$ that accepts precisely such strings, and we will then want to check whether it accepts a least ...
Only top voted, non community-wiki answers of a minimum length are eligible
