CS 4110 Flashcards
Regular Expressions/Regular Languages
(a+b)a(a+b)
Recursive Definitions
For positive integers:
Rule 1: 1 is in INTEGERS
Rule 2: If x is in INTEGERS, so is x+1
FA
Finite Automaton
A finite automaton is a collection of three
things
–A finite set of states, including one start state, and
zero or more final states(accepting states).
–An alphabet of possible input letters
–A finite set of transitions that tell for each state
and for each letter of the input alphabet which
state to go to next: nextState = f(input,
currentState)
(FA) start and stop states
“-” to represent start state
•“+” to represent final state
Deterministic
each move is completely
defined by the current spot and the input, no
context information is needed
Halting Problem
The Halting Problem is the problem of deciding or concluding based on a given arbitrary computer program and its input, whether that program will stop executing or run-in an infinite loop for the given input
CFG
Context Free Grammar
Grammar
•A grammar is the set of rules by which the
valid sentences in a language are constructed.
•Syntax are the rules that do not involve the
meanings of words.
•Using syntax as a way of defining a language in
addition to using RE, FA, and TG.
•Using a grammar to generate strings in the
language as well as to determine whether a
string is in a language.
Nonterminals and Terminals
•Terminals: the words that cannot be replace by
anything (designated by lowercase letters)
•Nonterminals: the words that must be replaced by
other things (designated by CAPITAL LETTERS).
•The sequence of applications of the rules that produces
the finished string of terminals from the starting
symbol is called a derivation or a generation of the
word. The grammatical rules are often referred to as
productions.
•The job of sentence production is not complete until all
the nonterminals have been replaced with terminals.
PDA
Push Down Automaton
PDA input
•Inputis presented on a tape rather than being
magically supplied by a user.
–The tape is divided into cellswith one input per
cell.
–A blank(∆) marks the end of the input. Blank is
not the same as the space character.
–The tape is read-only and we cannot go back
and re-read a cell.
•We have some new types of state – mostly to
formalize the notion of accepting and rejecting
input:
•We also have a Read state, drawn as a
diamond. From a read state we can have
multiple arrows representing transitions to
take if particular inputs have been read.
Pushdown stack
•Add a stack and two new actions POP and PUSH. –POP is like READ in that we branch according to the item popped. –PUSH just specifies the item to be pushed •Pushdown Automata (PDA) = FA + stack + POP + PUSH
READ state
consumes the next input symbol, possibly blank
POP state
pops the top stack item (also possibly blank
READ state
will have out-edges with labels from Σ
POP state
will have out-edges with labels from Γ
CNF
Chomsky Normal Form
TM
Turing Machine
Turing Machine Alphabet
An input alphabet ∑from which the initial tape contents are drawn
Turing Machine Tape
The tape which usually contains the input. (∆ is the symbol for a
blank or empty cell and is not a legal character in an alphabet)
Turing Machine Tape Head
The Tape Head which is initially positioned at the leftmost square
on the tape. It can in one step read the contents of a cell on the TAPE,
replace it with some other character, and reposition itself to the next
cell to the right or to the left of the one it has just read
Turing Machine Start/Halt states
which includes exactly one START state and a
number, possible zero, of HALT states
Turing Machine Program
A program as a set of rules to tell how to do a series of actions given
the current state and the input letter (quintuples: Qi Sr Sw Qj D,
Where the quintuple is interpreted as “if the machine is in state Qi and
the current tape symbol is Sr then write symbol Sw, go to state Qj and
move one square in direction D along the tape”
