New answers tagged automata
0
Here is a simpler proof. We will show that for every $\ell$, the equivalence relation $\equiv_L$ has at least $\ell$ equivalence classes.
Given $\ell$, find $n$ such that $3^{n+1} - 3^n \geq \ell$. Consider the $3^{n+1} - 3^n$ words $a^0,a^1,\ldots,a^{3^{n+1}-1-3^n}$. I claim that they are pairwise inequivalent. Indeed, suppose $0 \leq i < j \leq 3^{n+1}...
1
Yes, as long as your alphabet is defined as a set of different couples of binary digits
1
Call $(0+11^*0)$ as A and $(1+01^*0)$ as B. Then what you have on left-hand side is just: $$ R = A + AB^*B$$
Using Arden's Theorem we know that in this case: $$R = AB^*$$
Then what we have simplified is: $$(11^*0+0)(1+01^*0)^*$$
Another simplification using Arden's Theorem would give us:
$$(11^*+ \epsilon)0(1+01^*0)^*$$
Which is finally equivalent to: $$1^*...
3
I think you have to be more careful in the inductive steps, but it seems you basically have the argumentation ready. According to me proper induction would be
If $R_1$ and $R_2$ can be written as sum of products, then so can
$R_1\cdot R_2$, $R_1+R_2$ and $R_1^*$.
The proof could be completed as:
If $R_1$ and $R_2$ can be represented as sum of products ...
1
The two regular expressions describe the same language.
5
There is no known natural example of such a pair, and indeed there are various results in computability theory suggesting that such a pair does not exist. So to whip up an example one has to do some work.
The simplest approach (indeed, the easiest I know) is via mutual diagonalization: we build inductively a pair of increasing sequences of infinite binary ...
-1
If we are saying non deterministic Turing machine and LBA are same then its wrong.
If we say non deterministic Turing machine with limited space then we can call it as LBA.
LBA has space boundaries where as Turing machine don't have.
1
any location except i/p part means
(total unbounded tape area - tape area that includes i/p string)
= (infinity length - finite length) as we know i/p string length is always finite
= infinity length
in the definition of linear bounded automata it is stated that the tape can be used as a function of the input string length.but here the portion that can ...
5
The automaton is mainly used as a simple model of computation to check input strings on some defined conditions by reading the string and giving out whether the string is accepted in a defined language or not.
There are a lot of examples. A really crucial for example in terms of computing are the RegEx-expressions, if you heard of that. There are some ...
6
In computer science, "automaton" refers to some kind of finite state machine. This is a basic and fundamental model of computation, and automata are widely used in implementing simple electronic devices and in writing parsers, e.g., for programming languages.
0
Rice theorem can be applied when we are talking about languages of Turing machines, not about Turing machine behavior or characteristics themselves or anything else which is not related to "only" languages they accept.
You are talking about a narrow Rice's theorem. In Wikipedia, it states that
Rice's theorem can also be put in terms of functions: for ...
0
You're right that both of these are non-trivial properties. The key is, Rice's theorem applies only to non-trivial semantic properties.
So what defines a semantic property?
Intuitively, a "semantic" property is a property of what the machine does, rather than how the machine works. If you treat the machine as a black box that takes input and gives output, ...
1
Imagine an NFA with a single state, which is final/accepting. It has no edges.
This NFA accepts the language $\{\varepsilon\}$—that is, only the empty string. If it is given a non-empty string, it looks for appropriate edges leading away from the starting state, finds none, and fails.
0
The question shows several misconceptions. I'll try to clarify the key aspects.
If $L$ is recognizable but not decidable, then $L$ has to be infinite (otherwise, it is decidable). If a TM recognizes such $L$, it has to accept all the words in $L$ (by definition of "recognizes"), hence it must halt in infinitely many cases.
A TM halting on infinitely many ...
1
Note that you are bounding the maximal number of configurations, that the machine can be in, from above. To see it more clearly, when a TM $M$ runs on a finite word $w$ it induces a configuration tree $G = \langle V, E\rangle$ where:
$V$ is the set of configurations that $M$ can be in when it runs on $w$,
$q_0w$ is the initial configuration of $M$ on $w$ ...
Top 50 recent answers are included
