Automata Definition and 34 Threads

An automaton (; plural: automata or automatons) is a relatively self-operating machine, or control mechanism designed to automatically follow a predetermined sequence of operations, or respond to predetermined instructions. Some automata, such as bellstrikers in mechanical clocks, are designed to give the illusion to the casual observer that they are operating under their own power. Since long ago, the term is commonly associated with automated puppets that resemble moving humans or animals, built to impress and/or to entertain people.
Animatronics are a modern type of automata with electronics, often used for the portrayal of characters in films and in theme park attractions.

View More On Wikipedia.org
Recent contents Top users
  1. HrvojeDjurdjevic

    Von Neumann replicator vehicle model

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

    Optimizing and minimization of a Deterministic Finite Automata

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

    Comp Sci Regular Expression in Theory of Automata and Computation

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

    What is the sublanguage of L={ε, 1, 11, 111}

    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 {ε}...
  5. Giulio Prisco

    Reversible AND universal elementary cellular automata

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

    Calculate complexity of the game of life (cellular automata)

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

    Studying Value of learning the Theory of Computation and Automata

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

    I Are all Cellular Automata models of universes?

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

    A Can quantum cellular automata simulate quantum continuous processes?

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

    Computations Using Playing Cards

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

    Courses Taking Automata Theory and Analysis of Algorithms together?

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

    MHB Number of states of finite 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...
  13. T

    Help understanding Non-determinate Finite Automaton

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

    MHB Describe a language accepted by a pushdown automata.

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

    Can an AI write a credible novel with Wikipedia and YouTube?

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

    MHB Convert a non-deterministic finite automata to a regular expression.

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

    Difference between kleene star and a plus

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

    T hooft Cellular Automata Quantum Mechanics

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

    Automata theory: understanding different automata

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

    MHB What Automata Accepts Binary Numbers Divisible by $2 ^ k$?

    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?
  21. H

    What Are the Differences and Solutions for Automata Theory Language Constraints?

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

    Deterministic Finite Automata - Myhill Nerode

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

    MHB Answer: Language of Automata: DFA Q1, Q2

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

    Logic Matrices - automata theory

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

    Reversing a regular deterministic finite automata

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

    Constructing a DFA from a Regular Expression: How to Handle * and () Operators?

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

    Designing a DFA for L={vwv : v,w elements of {a,b}* and |v| =2}

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

    Automata: Trying to understand how to check if language is regular

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

    Lingusitics Can You Solve the Automata Language Problem?

    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!
  30. F

    Creating a 2D Cellular Automata with Modifications

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

    Quantum Automata: More than 1 Start State?

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

    Mathematica GridMathematica for parallel computing of cellular automata models

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

    Point of automata theory in ECE?

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

    How to Construct DFA and NFA for Languages Divisible by 6 or 10?

    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)
Back
Top