Automata theory

Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word automata comes from the Greek word αὐτόματος, which means "self-acting, self-willed, self-moving". An automaton (automata in plural) is an abstract self-propelled computing device which follows a predetermined sequence of operations automatically. An automaton with a finite number of states is called a Finite Automaton (FA) or Finite-State Machine (FSM). The figure on the right illustrates a finite-state machine, which is a well-known type of automaton. This automaton consists of states (represented in the figure by circles) and transitions (represented by arrows). As the automaton sees a symbol of input, it makes a transition (or jump) to another state, according to its transition function, which takes the previous state and current input symbol as its arguments. Automata theory is closely related to formal language theory. In this context, automata are used as finite representations of formal languages that may be infinite. Automata are often classified by the class of formal languages they can recognize, as in the Chomsky hierarchy, which describes a nesting relationship between major classes of automata. Automata play a major role in the theory of computation, compiler construction, artificial intelligence, parsing and formal verification. The theory of abstract automata was developed in the mid-20th century in connection with finite automata. Automata theory was initially considered a branch of mathematical systems theory, studying the behavior of discrete-parameter systems. Early work in automata theory differed from previous work on systems by using abstract algebra to describe information systems rather than differential calculus to describe material systems. The theory of the finite-state transducer was developed under different names by different research communities.

Ontology

Official source

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Related exercises (9)

Irregular tube

An incompressible liquid circulates in a tube. At a certain location, the section of the tube strongly decreases (cf. figure). The continuity equation indicates us that :

\frac{\partial\rho}{\partial t} + \nabla\cdot \rho \vec{v} = 0~.

Show that this is equivalent to the simpler equation:

\quad \langle v_n\rangle=\frac{1}{S_n}\iint_{S_n}\vec{v}\cdot d\vec{\sigma} ~.$$ If we add to the figure the velocity vectors as well as the vect

Loop the loop

A stuntwoman attempts to drive her car weighing mg around a vertical looping track of radius R. She enters the track at point P with velocity V⃗_(P) and we assume that she then free-wheels around the track without either braking or accelerating. There is no friction.

Write the car’s equations of motion for the entire loop.
Express the car’s mechanical energy at all points of the loop, and show that the mechanical energy is a simple integral of the motion.
Compute the reaction force from t

The hare and the turtle

A hare and a turtle race over a distance L. The turtle starts running at constant speed

v_{\rm t}

and the hare at constant speed

v_{\rm h}

. The hare is not taking this seriously, and so

v_{\rm h} < v_{\rm t}

. When the turtle reaches a bridge that stands at a distance L′u2004

Bungee jumping

A student with mass m, attached to an elastic cord with spring constant k, jumps without any initial speed from a bridge at height h above the river. The elastic cord barely stops the student from touching the river. We neglect friction. We suggest defining a y-axis pointing upwards and with its origin at river height.

Using the conservation of total mechanical energy, show that the cord’s rest length l₀ is $l_0=h-\sqrt{\frac{2mgh}{k}}$ .
Show that, while jumping, the student reached maximal sp

Excitation of a vertical harmonic oscillator

A mass m is suspended on a spring of natural length l₀ and of elastic constant k. The spring is attached to a piston. The vertical motion of the piston is described by the equation s(t)u2004=u2004s₀cosu2006(ωt)xa0.

Give explicit expressions for the external forces and determine the equation of motion.
Show that the equation of motion can be recast as, $\ddot{x}\left(t\right) + c_1\,x\left(t\right) = c_1\,s\left(t\right)\ ,$ where x(t)u2004=u2004z(t)u2005+u2005c₂ with z(t) the vertica

Related notebooks (6)

Implementation and Analysis of FIR Filters

Digital filters are fully described by their constant-coefficient difference equation (CCDE) and a CCDE can be easily translated into a few lines of code to obtain a simple filter implementation. In the case of FIR filters the coefficients in the CCDE coincide with the values of the impulse response, so that FIR filters can also be implemented as a convolution (aka an inner product) or by performing a multiplication in the frequency domain, as we will see shortly. When applying an FIR filter to a finite-l

Voice Transformation Techniques Using Digital Signal Processing

A Gallery of Voice Transformers[1]¶

                                      [2]Paolo Prandoni, [3]LCAV, EPFL

In this notebook we will explore various ways to implement a system that changes the voice of a speaker. Typical applications for these techniques, strictly sorted by plausibility, include international spy missions and prank telephone calls, and devices such as the one displayed here can be easily bought on the web... or in a novelty shop. No description has been provided for t

Designing FIR Filters Using the Parks-McClellan Algorithm

The Parks-McClellan Filter Design Method[1]¶

                                      [2]Paolo Prandoni, [3]LCAV, EPFL

The Parks-McClellan (PM) algorithm is a clever application of advanced polynomial fitting techniques to the problem of FIR filter design. In this notebook we will explore the key ideas behind the method by considering the design of a simple Type-I lowpass filter. NOTE: This notebook uses interactive widgets. If the interactive controls do not work or show up, please fo

Whistle-Activated Keylock System Implementation

Whistling Keylock[1]¶ In this notebook we will implement a simple "whistle-activated" keylock, that is, an access control system where the password is a pre-defined melody. To program the lock, you record your musical passphrase and then, to open the lock, you whistle it back. Although the implementation will be simple and skip most of the fine details that would be necessary to produce a truly robust system, we need to take into account at least the following points: * The syste

Exploring Quantization and Oversampling through One-Bit Music

One-Bit Music[1]¶ In this notebook we will talk about quantization and oversampling and we will do so by taking a trip down memory lane to revisit the early from monophonic square waves, introduce polyphony by way of pulse-width modulation and finish with the basics of sigma-delta quantization. pacman In [1]: import matplotlib import matplotlib.pyplot as plt import numpy as np import scipy.signal as sp from scipy.io import wavfile import IPython In [2]: import sys ! wget -q -O mus