Flashcards
CS1005 Lecture 2
Cards in this deck (12)
- 1What is automata theory?This theory deals with the logic of computation with respect to simple machines, referred to as automata.
- 2What does Automata theory help with?Through automata, computer scientists are able to understand how machines compute functions and solve problems.
- 3What are Automatons?Automatons are abstract models of machines that perform computations on an input by moving through a series of states or configurations.
- 4What are some examples of automated machines?Finite state machine and Turing machine
- 5What are state transition diagrams?A diagram which allows you to visually see the different states of the automation and how to move from one state to another.
- 6What are the different elements of a state transition diagram?Circles (Nodes) represent a state,
Arrows represent state transitions
Each arrow also represents one instruction.
An arrow is labelled with: current symbol (input), new symbol (output) and direction. - 7What is a State Transition Table used for?The state transition table lists all possible combinations of the present state and the inputs
- 8What is a Turing Machine?A Turing Machine is a finite state machine plus a tape memory
- 9Describe Finite State MachinesThey are simplest model of computation.
They are a small computer or controller
They have a start state - 10What is the data structure a Turing Machine uses?An Infinite Tape
- 11Describe a State Machine for a Turing MachineIt is a Finite State Machine
It has an initial state
It has a final state
The machine may enter into a LOOP where we do not stop.
It is a deterministic machine - 12What are the differences between FSMs & Turing Machines?We can see that Turing Machines can be visualised as FSMs
A Turing machine is a finite state machine plus a tape memory.
Information
- Description
- Year 1 undergraduate CS1005 Logic and Computation Flashcards on CS1005 Lecture 2, created by Y H on 03/11/2021.
- Created by
- Y H
- Views
- 1
- Rating