CS 4110

Question 1

Regular Expressions/Regular Languages

Answer 1

(a+b)a(a+b)

Question 2

Recursive Definitions

Answer 2

For positive integers:
Rule 1: 1 is in INTEGERS
Rule 2: If x is in INTEGERS, so is x+1

Question 3

FA

Answer 3

Finite Automaton

Question 4

A finite automaton is a collection of three

things

Answer 4

–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)

Question 5

(FA) start and stop states

Answer 5

“-” to represent start state

•“+” to represent final state

Question 6

Deterministic

Answer 6

each move is completely
defined by the current spot and the input, no
context information is needed

Question 7

Halting Problem

Answer 7

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

Question 8

CFG

Answer 8

Context Free Grammar

Question 9

Grammar

Answer 9

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

Question 10

Nonterminals and Terminals

Answer 10

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

Question 11

PDA

Answer 11

Push Down Automaton

Question 12

PDA input

Answer 12

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

Question 13

Pushdown stack

Answer 13

•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

Question 14

READ state

Answer 14

consumes the next input symbol, possibly blank

Question 15

POP state

Answer 15

pops the top stack item (also possibly blank

Question 16

READ state

Answer 16

will have out-edges with labels from Σ

Question 17

POP state

Answer 17

will have out-edges with labels from Γ

Question 18

CNF

Answer 18

Chomsky Normal Form

Question 19

TM

Answer 19

Turing Machine

Question 20

Turing Machine Alphabet

Answer 20

An input alphabet ∑from which the initial tape contents are drawn

Question 21

Turing Machine Tape

Answer 21

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)

Question 22

Turing Machine Tape Head

Answer 22

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

Question 23

Turing Machine Start/Halt states

Answer 23

which includes exactly one START state and a

number, possible zero, of HALT states

Question 24

Turing Machine Program

Answer 24

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”

Question 25

Relationship between TM and Recursively Enumerable Language

Answer 25

A language (L) is recursively enumerable if there is a
TM that
–Accepts every word in L
–Crashes or loops for every word in L’

Question 26

2PDA

Answer 26

2PDA: a deterministic PDA with 2 stacks

Question 27

Relationship between 2PDA and TM

Answer 27

•2PDA = TM

–All operations of 2PDA can be simulated by a TM.

Question 28

How can you solve the halting problem?

Answer 28

Humans can’t solve the halting problem

Question 29

When is a grammar in Chomsky Normal Form?

Answer 29

a context-free grammar, G, is said to be in Chomsky normal form if all of its production rules are of the form: A → BC, or A → a, or S → ε, where A, B, and C are nonterminal symbols, the letter a is a terminal symbol, S is the start symbol, and ε denotes the empty string