Automata Definition and 34 Threads

In his paper "Theory of self-reproducing automata", Von Neumann asserted that it is in principle possible to set up a self-reproducing automaton that consists of the following automata: A scanner - given an object X returns a description of X B builder - given a description of X...

so this is the question , I have to minimize this DFA this is How I did it but when I checked for answers , this is what it was, can someone please explain to me what mistake I made? I have been wondering about this for past 2 days

In first part,since every block of 4 consecutive symbol contain at least 2 a's The answer in notes is given (aa(a+b)(a+b)+a(a+b)a(a+b)+a(a+b)(a+b)a+(a+b)aa(a+b)+(a+b)a(a+b)a+(a+b)(a+b)aa)+ But this wont be true since if we choose aabbbbaa which is possible according to the above regular...

TL;DR Summary: [Formal languages and automata] Show all sublanguages of the language L={ε, 1, 11, 111} on Σ={0, 1}. [Formal languages and automata] Show all sublanguages of the language L={ε, 1, 11, 111} on Σ={0, 1}. Is the answer {1}, {11}, {111}, {1, 11}, {11, 111}, {1, 11, 111}? Or {ε}...

Has any of the reversible extensions of the elementary one-dimensional cellular automata described by Wolfram in NKS (e.g. Rule 37R) been shown to be computationally universal (like Rule 110)? If so, please give me links. Otherwise, could this be the case? Or is there a proof that no nR can be...

I want to calculate the kolmogorov complexity of n evolution of a game of game of life(game of life is a kind of cellular automata). I’m not searching for the complexity of a certain pattern of cells but for the total complexity of an initial set of cells over n evolutions. Does it make sense to...

This may be a somewhat disorderly, unplanned out question, but nonetheless, I don’t know whether or not there exist any suitable academic advising websites that would be suitable for posting such. Would it be worthwhile investing time into learning theory of computation and automata via Neso...

Both Stephen Wolfram and nobel laureate Gerard 't Hooft think that the universe is a Cellular Automata. As far as I know, 't Hooft developped a series of frameworks to build different models of Cellular Automata and Wolfram also proposed a framework where network nodes could produce different...

Can quantum cellular automata/quantum game of life simulate quantum continuous processes in the continuous limit? At the end of this article: https://hal.archives-ouvertes.fr/hal-00542373/document it is said that: "For example, several works simulate quantum field theoretical equations in the...

EXPLORING THE POSSIBILITY OF PERFORMING COMPUTATIONS WITH PLAYING CARDS I was listening to an interview with John Conway yesterday and the conversation turned to his "Game of Life". Conway mentioned that Life can be configured in such a way that it can perform arbitrary computations. This got...

So I'm at a bit of a cross roads. For this summer semester, due to class restrictions I can only take either operating systems with Automata Theory, or Analysis of Algorithms with Automata Theory. I've heard from many people that Algorithms is a nightmare, and I'm not sure if taking Automata...

Hey! :o Prove that for each $n>0$, a language $B_n$ exists where $B_n$ is recognizable by an NFA that has $n$ states, and If $B_n=A_1 \cup \dots \cup A_k$, for regular languages $A_i$, then at least one of the $A_i$ requires a DFA with exponentially many states. Could you give me some...

Homework Statement There's not a particular problem, per se, just that I seem to be missing something with my understanding of how to evaluate a string against a non-deterministic finite automaton with epsilon transitions. But one I've been working with is shown below Homework Equations NA...

That's the question. I've had a go at drawing a diagram to help me explain it. My understand is that from the start state, an A pushes an A to the stack and stays in the initial state s. Getting a B whilst in state s pops an A from the stack and moves to final state f. Getting a B whilst in...

I always wanted to create a toolbox of critical analysis tools for young people to analyze, debate, and anticipate the near term future given our human nature and our history, especially since the scientific revolution. This is what my novel is intended to do, but writing a first (crap) edition...

Hi, I'm trying to covert a NFA to a regular expression and I've manged to come up with an answer but I don't think that it is right. Here's the question - http://i.imgur.com/NUHxTXY.png And here's my workings -...

Homework Statement So this isn't a question from a homework directly, but it's been used in my textbook an I'm not sure of the difference. For example, if I have a* and a+, what is the difference Homework Equations The exact wording in the book was {0,1}* and {0,1}+ The Attempt at a Solution...

Is t hooft's model of (deteministic) quantum mechanics a viable model? http://arxiv.org/pdf/1207.3612.pdf http://arxiv.org/pdf/1405.1548.pdf http://arxiv.org/pdf/1308.1007.pdf

Move this thread to appropriate sub-forum if not here. I'm studying automata theory and I'm having trouble understanding different machines or automata. First one is regular language. This is the simplest machine with different states and we can switch depending on what our input is. Very...

Hey! :o "Give the definition of a FA (without a graphical representation), which accepts binary numbers $n$ which are without remainder divisible by $2 ^ k$ for all $k \in \mathbb{N} \setminus \{0\}$." Could you help me understanding which automata is meant?

Im currently studying Automata Theory and i have these questions that i want to answer the problem I am not sure if i answer them currently can anyone help me to solve them properly

Homework Statement Let ## f\left( b_{1}, \dots , b_{n} \right) ##be a boolean function. Define ##S_{f} = \{\left( b_{1}, \dots , b_{n} \right): f\left( b_{1}, \dots , b_{n} \right)=1; b_{i} \in \{0,1\}, 1\leq i \leq n \}##The subsets ##S_{f}## are viewed below as languages consisting of...

Hi! Could you help me finding the language that is accepted by the DFA with the following state diagram? ___| a ____ b Q1 | Q2 __ Q1 Q2 | Q2 __ Q3 Q3 | Q3 __ Q3 final states: Q1, Q2

Hi, First let's say you have an input vector and an output vector describing states. Let us use a binary number system, it doesn't really matter for mathematics. Say, I have an input vector V, components v_i. Now I would like to have an output vector W which can be of other dimension. The...

I have seen descriptions for an algorithm that can take a regular deterministic finite automata and create a non-deterministic finite automata that is guaranteed to generate the reverse of string accepted by the DFA. Does anyone know of a "formal" proof that shows this is true in all cases...

Homework Statement Construct a DFA based on the regular express. Regular expr = *a(ab)*c* Homework Equations How do you construct a DFA out of this regular expr? The Attempt at a Solution Here's what I think it says... it can accept 0 or more a,c, and ordered pair of ab...

L={vwv : v,w elements of {a,b}* and |v| =2} I know that "v" can take either aa, ab, ba or bb as values. I also know that "w" can be any string containing "a" and "b". Overall, I know that the two first and two last characters must be identical. How would I show this in a DFA or even an NFA...

Homework Statement Prove or Disprove L is regular, where L = {0^{i}1^{j} | (i^{2} + j^{2}) is square}Homework Equations N/AThe Attempt at a Solution I tried using pumping lemma, but I don't know how to assign p if there are two variables (i and j)... I understand the i^{2} + j^{2} would be...

Let L be the language with alphabet {0, 1}. L:={ w in {0, 1}* | number of 0 divisible by 5, number of 1 divisible by 3} Find a deterministic finite automata & regular expression that express L. Sorry, but this is sort of a problem that i got stuck in a book. Help me, please!

I'm looking to create a two-dimensional cellular automata. And I suck at programming, esp if graphics are involved. Is there anything out there where you can program the rules for a CA and I can just let it run whilst watching it? I will need some extensive modifications... Requirements of...

Unlike normal finite automata, which always have one start state, it seems that quantum automata can actually have more than one start state. How would one be able to use this as a real physical computer, if by pressing the power button on your computer it might not start - but, rather morph...

Hi, I'm interessed in using GridMathematica for parallel computing of cellular automata models. I know using mathematica so the syntax shouldn't be a problem. however, I wonder if there's here someone who has worked with it since I would like to know if the program is worth the cost etc...

So I've got a ton of time on my hands for the next few days so I'm trying to meticulously plan out the courses I'm going to take in grad school in electrical engineering. Some things look interesting, and I've been trying to plan my curriculum the best I can to coincide with things that would...

L = {a^k / k is divisible by 6 or 10 (or both)} Give a DFA and NFA for the above. Can anyone do it? My 2 cents: This is my DFA for the above language. (q_x) = accepting state where x is any integer. >q_0-->q_1--> ... (q_6)...q_28--->(q_30)