Ch 13

Question 1

A stack machine is a kind of automation that uses a stack for auxiliary data storage.

Answer 1

T

Question 2

The size of the stack is bounded.

Answer 2

F

Question 3

The size of a stack is unbounded - it never runs out of space.

Answer 3

T

Question 4

The set of languages that can be defined using a stack machine is the same as the set of languages that can be defined using a DFA: the regular languages.

Answer 4

F

Question 5

What gives stack machines an edge over finite automata?

Answer 5

The size of the stack is unbounded.

Question 6

What is a stack?

Answer 6

A collection of data accessed in last-in-first-out order.

Question 7

What is a kind of automation that uses a stack for auxiliary data storage?

Answer 7

Stack machine

Question 8

What does it mean for data to be pushed onto a stack?

Answer 8

Data item is added to the top of the stack.

Question 9

What is it called when data is added to a stack?

Answer 9

Push

Question 10

Just like DFAs, stack machines make state transitions.

Answer 10

F

Question 11

Stack machines make transitions.

Answer 11

F

Question 12

Unlike a DFA or NFA, what does a stack machine not do, but instead maintains a stack of symbols?

Answer 12

state transitions.

Question 13

A stack machine starts with a stack that contains just one symbol, S

Answer 13

T

Question 14

No stack machine can be deterministic.

Answer 14

F???

Question 15

NA stack machine may have more than one legal sequence of moves on a given input string.

Answer 15

F

Question 16

If the stack machine decides to accept the input string, it will by leaving its stack empty, and popping everything off including what?

Answer 16

The bottom-of-stack symbol S.

Question 17

What does a stack machine start with?

Answer 17

A start symbol, S

Question 18

In a stack machine, what must be popped off to signal that the input string is accepted?

Answer 18

The original bottom-of-stack symbol S

Question 19

The transition function (pikmen) takes only one parameter.

Answer 19

F

Question 20

A stack machine is a 4-tuple.

Answer 20

T

Question 21

A stack machine is nondeterminisitic - at each stage, there may be any number of possible moves.

Answer 21

T

Question 22

A stack machine is nondeterministic.

Answer 22

T

Question 23

At each stage of a stack machine, there may be only two possible moves.

Answer 23

F

Question 24

What is the formal definition of a stack machine?

Answer 24

See notes

Question 25

What is the output of the transition function?

Answer 25

A set of strings that can be pushed onto the stack.

Question 26

What is Γ of 4-tuple M

Answer 26

Stack alphabet

Question 27

What is Σ of 4-tuple M

Answer 27

Input alphabet

Question 28

What is S of 4-tuple M

Answer 28

An element of Γ is the initial stack symbol

Question 29

An instantaneous description of a Stack machine is a pair (x,y).

Answer 29

T

Question 30

There is at least one move if the Stack Machine's stack is empty.

Answer 30

F

Question 31

No move is possible when the stack machine is empty.

Answer 31

T

Question 32

At any point in the stack machine's operation, its future depends on two things: that part of the input string that is still to be read, and what?

Answer 32

The current contents of the stack.

Question 33

An instantaneous description for a stack machine is a pair (x, y) where x ∈ Σ* is what?

Answer 33

the unread part of the input.

Question 34

What side of the stack is considered to be the top of the stack?

Answer 34

???

Question 35

A stack machine can easily simulate any finite automation.

Answer 35

T

Question 36

A stack machine cannot easily simulate a finite automation.

Answer 36

F

Question 37

What can a stack machine easily simulate?

Answer 37

Finite automation.

Question 38

What process can be carried out by a stack machine, using the stack to hold the string to be rewritten?

Answer 38

String-rewriting

Question 39

when can a stack machine be used to replace a leftmost symbol?

Answer 39

If the leftmost symbol is a nonterminal

Question 40

There is no CFG that we can construct a stack machine for.

Answer 40

F

Question 41

We can take any CFG and construct a stack machine for the same language.

Answer 41

T

Question 42

When constructing a stack machine out of a CFG, what should be done if the top symbol on the stack is nonterminal?

Answer 42

replace it using any one of the grammar's productions for that nonterminal

Question 43

What does a stack machine recognize?

Answer 43

???

Question 44

There is a way to take any stack machine and construct a CFG for the same language.

Answer 44

T

Question 45

It is not possible to take any CFG and construct an equivalent stack machine. However, the reverse of this is true.

Answer 45

F

Question 46

If M = (Γ, Σ, S, δ) is any stack machine, there is no context-free grammar G with L(G) = L(M).

Answer 46

F

Question 47

If M = (Γ, Σ, S, δ) is any stack machine, there is context-free grammar G with L(G) = L(M).

Answer 47

T

Question 48

In the construction, the stack symbols of the stack machine become nonterminals in the constructed grammar, and the input symbols become what?

Answer 48

terminals

Question 49

A language is context free if and only if it is L(M) for some stack machine M.

Answer 49

T

Question 50

CFGs and stack machines have equivalent definitional power.

Answer 50

T

Question 51

When is a language context free?

Answer 51

If and only if it is L(M) for some stack machine M

Question 52

Forcing a parse tree to repeat a nonterminal symbol in a certain way is called _______ parse trees.

Answer 52

pumping parse trees

Question 53

The height of a parse tree is the number of edges in the longest path from the start symbol to any leaf

Answer 53

T

Question 54

The ___ of a parse tree is the number of edges in the longest path from the start symbol to any leaf.

Answer 54

height

Question 55

If L1 and L2 are any context free language, L1L2 is also context free.

Answer 55

T

Question 56

Context free languages are closed for some of the same common operations as regular languages.

Answer 56

T

Question 57

What are some of the same common operations that context-free languages are closed for?

Answer 57

union, concantenation, kleene star

Question 58

The Kleene closure of any language L is L* = {x1x2…xn | n ≥ 0, with allxi ϵ L}.

Answer 58

T

Question 59

If L is any context free language, L* is also context free.

Answer 59

T

Question 60

Context-free languages are closed under what with regular languages?

Answer 60

intersection

Question 61

the CFLs are closed for complement.

Answer 61

F

Question 62

The intersection of regular languages is a regular language, and they are not all CFLs

Answer 62

F

Question 63

The intersection of 2 CFLs fails to be a CFL

Answer 63

F

Question 64

In nonclosure property, what does not mean that every intersection of CFLs fails?

Answer 64

???

Question 65

CFLs are not closed for which operations?

Answer 65

intersection or complement

Question 66

The pumping lemma is very useful for proving that languages are context free.

Answer 66

T

Question 67

For a certain class of grammars, the non determinism of the top-down-parsing stack machine can easily be avoided.

Answer 67

T

Question 68

Whenever there is a terminal on top of the stack, the constructed stack machine can apply any one of the productions for that nontermina.

Answer 68

T

Question 69

The constructed stack machine works by repeatedly applying what?

Answer 69

productions

Question 70

PDAs can be illustrated with state-transition diagrams.

Answer 70

T

Question 71

One widely studied kind of automation is the push down automations.

Answer 71

T

Question 72

Push down automation has a limited, bounded stack of symbols.

Answer 72

F

Question 73

Some PDAs accept a string by empying their stack, some accept by ending in an acepting state, and some must do both.

Answer 73

T

Question 74

Some push-down automations start with a special symbol on the stack.

Answer 74

???

Question 75

What is the definition of a PDA?

Answer 75

A finite-state machine augmented with an unbounded stack of symbols.

Question 76

What does PDA stand for?

Answer 76

Push-down automation

Question 77

what automation is like a finite state machine augmented with an unbouded stack of symbols?

Answer 77

Push-down automation

Question 78

a deterministic context-free language (DCFL) is a regular language that is L(M) for some DPDA M.

Answer 78

T

Question 79

The set of languages that cna be recognized by a PDA is not the same as a stack machine.

Answer 79

???

Question 80

DPDAs are usually defined in a way that prevents them to get stuck in most configurations.

Answer 80

F

Question 81

What is a deterministic context-free language?

Answer 81

???

Question 82

A ___ is a language that is L(M) for some DPDA M.

Answer 82

Deterministic context-free language

Question 83

What is a deterministic context-free language (DCFL)

Answer 83

a language that is L(M) for some DPDA M

Question 84

What happens when you restrict PDAs to the deterministic case?

Answer 84

???

Question 85

The DCFLs have the same closure properties of CFLs.

Answer 85

F

Question 86

The union of two DCFLs is necessarily a DCFL.

Answer 86

F

Question 87

The DCFLs are the same as the LR(1) language. These are exactly the languages that can be quickly parsed using deterministic, bottom-up techniques.

Answer 87

T

Question 88

There is no tool like the pumping lemma specifically for DCFLs.

Answer 88

T

Question 89

What is the result for xR if we know x=abc?

Answer 89

cba