Untitled

Turing Machine

A model of an abstract machine proposed by Alan Mathison Turing in 1936 that could perform any computational process carried out by present-day computers

Finite Automata Model (1943)

A formal version of the finite automata model proposed by Warren McCulloch and Walter Pitts in relation to neural networks

Mealy and Moore Machine

A complete form of finite automata and finite state machine built around 1960 by George Mealy and Edward Moore

Automata Theory

The study of the logic of computation with respect to simple abstract machines called automata, derived from the Greek word "automatos"

Lexical Analyzer

The first phase of compilers designed by finite automata

Automaton

A logically defined system or entity where materials, energy, or information are transformed and transmitted to perform operations without direct human participation

Input (Automaton Characteristic)

Data taken in each clock pulse from a finite set called the input alphabet

Output (Automaton Characteristic)

Data generated in each clock pulse from a finite set called the output alphabet set

State (Automaton Characteristic)

The condition in which the automaton resides at any discrete instance of time, belonging to a set Q

State Transition

A function of the present state and present input that determines the next state in which the automaton resides

Output Relation

A relation where the output depends either on the present state and present input or on the present state only

Finite Automata (FA)

Machine formats of a regular expression (type 3 grammar) defined by a 5-tuple M = {Q, Σ, δ, q0, F}

Input Tape

A component of FA containing input symbols divided into squares, placed between a left end marker and a right end marker

Reading Head

A component of FA that scans each square in the input tape to read input, moving primarily from left to right

Finite Control

The control unit of an FA containing state transition relations that determines state changes based on current state and input

Deterministic Finite Automata (DFA)

A type of finite automaton where there exists a single path for a specific input from the current state to the next state, and no null moves are allowed

Dead State

A state where the control unit enters and remains confined with no way out, causing the string processing to end or fail

Nondeterministic Finite Automata (NFA)

A type of finite automaton where multiple paths (next states) can exist for a specific input from the current state

ε Transition

A transition in an NFA that takes place without consuming any input character (a null string)

Mealy Machine

A type of finite automaton with output where the output depends on both the present state and the present input

Moore Machine

A type of finite automaton with output where the output depends on the present state only