Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Foundations 1 > Ch 13 > Flashcards

Ch 13 Flashcards

1
Q

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

A

T

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

The size of the stack is bounded.

A

F

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A

T

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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.

A

F

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What gives stack machines an edge over finite automata?

A

The size of the stack is unbounded.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is a stack?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A

Stack machine

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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

A

Data item is added to the top of the stack.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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

A

Push

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Just like DFAs, stack machines make state transitions.

A

F

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Stack machines make transitions.

A

F

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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

A

state transitions.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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

A

T

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

No stack machine can be deterministic.

A

F???

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

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

A

F

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

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

A

The bottom-of-stack symbol S.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What does a stack machine start with?

A

A start symbol, S

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

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

A

The original bottom-of-stack symbol S

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

The transition function (pikmen) takes only one parameter.

A

F

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

A stack machine is a 4-tuple.

A

T

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

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

A

T

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

A stack machine is nondeterministic.

A

T

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

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

A

F

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What is the formal definition of a stack machine?

A

See notes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

What is the output of the transition function?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

What is Γ of 4-tuple M

A

Stack alphabet

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

What is Σ of 4-tuple M

A

Input alphabet

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

What is S of 4-tuple M

A

An element of Γ is the initial stack symbol

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

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

A

T

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

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

A

F

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

No move is possible when the stack machine is empty.

A

T

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

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?

A

The current contents of the stack.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

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

A

the unread part of the input.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

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

A

???

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

A stack machine can easily simulate any finite automation.

A

T

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

A stack machine cannot easily simulate a finite automation.

A

F

37
Q

What can a stack machine easily simulate?

A

Finite automation.

38
Q

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

A

String-rewriting

39
Q

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

A

If the leftmost symbol is a nonterminal

40
Q

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

A

F

41
Q

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

A

T

42
Q

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

A

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

43
Q

What does a stack machine recognize?

A

???

44
Q

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

A

T

45
Q

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

A

F

46
Q

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

A

F

47
Q

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

A

T

48
Q

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

A

terminals

49
Q

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

A

T

50
Q

CFGs and stack machines have equivalent definitional power.

A

T

51
Q

When is a language context free?

A

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

52
Q

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

A

pumping parse trees

53
Q

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

A

T

54
Q

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

A

height

55
Q

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

A

T

56
Q

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

A

T

57
Q

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

A

union, concantenation, kleene star

58
Q

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

A

T

59
Q

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

A

T

60
Q

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

A

intersection

61
Q

the CFLs are closed for complement.

A

F

62
Q

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

A

F

63
Q

The intersection of 2 CFLs fails to be a CFL

A

F

64
Q

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

A

???

65
Q

CFLs are not closed for which operations?

A

intersection or complement

66
Q

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

A

T

67
Q

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

A

T

68
Q

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

A

T

69
Q

The constructed stack machine works by repeatedly applying what?

A

productions

70
Q

PDAs can be illustrated with state-transition diagrams.

A

T

71
Q

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

A

T

72
Q

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

A

F

73
Q

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

A

T

74
Q

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

A

???

75
Q

What is the definition of a PDA?

A

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

76
Q

What does PDA stand for?

A

Push-down automation

77
Q

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

A

Push-down automation

78
Q

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

A

T

79
Q

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

A

???

80
Q

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

A

F

81
Q

What is a deterministic context-free language?

A

???

82
Q

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

A

Deterministic context-free language

83
Q

What is a deterministic context-free language (DCFL)

A

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

84
Q

What happens when you restrict PDAs to the deterministic case?

A

???

85
Q

The DCFLs have the same closure properties of CFLs.

A

F

86
Q

The union of two DCFLs is necessarily a DCFL.

A

F

87
Q

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.

A

T

88
Q

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

A

T

89
Q

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

A

cba

Foundations 1 (5 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions