# Tag Info

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.

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 ...

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 ...

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

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^*...

1

The two regular expressions describe the same language.

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.

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 ...

Only top voted, non community-wiki answers of a minimum length are eligible