Cum. Final

Question 1

The empty set can be written as ∅ or {}.

Answer 1

T

Question 2

The concatenation of two strings x and y is the string containing all symbols of x in the order, followed by all the symbols of y in order.

Answer 2

T

Question 3

For any string x, xɛ = ɛx = x.

Answer 3

T

Question 4

{} = {ɛ}

Answer 4

F

Question 5

The Kleene closure of an alphabet can be a finite set.

Answer 5

T

Question 6

A language is a sequence over some fixed alphabet.

Answer 6

F

Question 7

The language defined by a DFA M is the set of strings over Σ.

Answer 7

F

Question 8

In a state transition diagram, the labels of states can impact the behavior of the machine being represented.

Answer 8

F

Question 9

A string x ∈ Σ* is accepted by a DFA M = (Q,Σ,δ,q0, F) if and only if δ*(q0,x)∈F.

Answer 9

T

Question 10

The regular languages are closed under complement.

Answer 10

T

Question 11

If L1 and L2 are languages, the intersection of L1 and L2 is L1 ∩ L2 = {x|x∈L1 or x∈L2}

Answer 11

F

Question 12

If L is a regular language, its complement must also be a regular language.

Answer 12

T

Question 13

Regular languages are not closed under intersection.

Answer 13

F

Question 14

Regular languages are closed under union.

Answer 14

T

Question 15

What is the definition of an alphabet?

Answer 15

An alphabet is a non-empty, finite set of symbols.

Question 16

What is the definition of a string?

Answer 16

A string is a finite sequence of zero or more symbols.

Question 17

How many elements are in {ɛ}

Answer 17

1

Question 18

The Kleene closure of an alphabet Σ, written Σ*, contains what?

Answer 18

The set of all strings over Σ.

Question 19

What is the definition of a language?

Answer 19

A set of strings over some fixed alphabet.

Question 20

What indicates the accept state in a state transition diagram?

Answer 20

A double circle.

Question 21

How is the start state indicated in a state transition diagram?

Answer 21

An arrow.

Question 22

What kinds of languages are recognized by DFAs?

Answer 22

regular languages.

Question 23

What set operation forms the set of all pairs using elements from two sets?

Answer 23

Cartesian Cross Product.

Question 24

What is the only difference between the product construction of the DFA for the union of two languages and the DFA for the intersection of the same two languages?

Answer 24

The intersection only accepts both accept states from the languages. The union will accept either or both accept states.

Question 25

A DFA has exactly one transition from every state for every symbol in the alphabet.

Answer 25

T

Question 26

An NFA can be thought of as a special kind of DFA.

Answer 26

F

Question 27

A DFA can make a state transition spontaneously, without consuming an input symbol.

Answer 27

F

Question 28

ɛ transitions are especially useful for combining smaller automata into larger ones.

Answer 28

T

Question 29

If S is a set, the powerset of S is P(S) = {R|R⊆S}

Answer 29

T

Question 30

For any NFA, there is a DFA that recognizes the same language.

Answer 30

T

Question 31

Any symbol a∈Σ is a regular expression with L(a) = {a}

Answer 31

T

Question 32

The special symbol ɛ is a regular expression with L(ɛ) = {ɛ}.

Answer 32

T

Question 33

The special symbol ∅ is regular expression with L(∅) = {ɛ}.

Answer 33

F

Question 34

If L is a language, the Kleene close of L is L* = {x1x2...xn | n≥0, with all xi ∈L}

Answer 34

T

Question 35

In a regular expression without parentheses, * has highest precednece and + has lowest precedence.

Answer 35

T

Question 36

The regular expression L((a+b)*) = L((a*+b*)).

Answer 36

F

Question 37

DFAs, NFAs , and regular expressions all have equal power for defining languages.

Answer 37

T

Question 38

Every regular language has a unique minimum-state NFA.

Answer 38

F

Question 39

The squaring extension adds the ability to define new languages

Answer 39

F

Question 40

What does NFA stand for?

Answer 40

Non-deterministic Finite Automata

Question 41

In (q,x) an instantaneous description of an NFA, what are q and x?

Answer 41

q= current state, x=unread part of string.

Question 42

The regular expression for an infinite, regular language must contain what operation?

Answer 42

*

Question 43

What is the language for the regular expression: b*a?

Answer 43

[b*a}

Question 44

What does the Unix tool egrep do?

Answer 44

egrept searches a file for lines that contain a sub-string matching a specified pattern.

Question 45

What does the "." symbol do when used as input to the Unix tool egrp?

Answer 45

Matches any symbol (except the end-of-line marker).

Question 46

What method is often used to define the token of a language when designing a compiler?

Answer 46

Write a collection of regexps.

Question 47

Give the formal definition of a NFA.

Answer 47

A non-deterministic finite automaton M (Q, Σ,δ,q0, F) where: Q is the finite set of states. Σ is the alphabet. δ∈(Qx(Σ∪{ɛ})→P(Q)) is the transition function. q0∈Q is the start state. F⊆Q is the set of accepting states.

Question 48

When doing derivation, there can be more than one place in a string where a rule can be applied.

Answer 48

T

Question 49

When two sets are disjoint, they have no common elements.

Answer 49

T

Question 50

The language {a^n b^n| is a regular language.

Answer 50

F

Question 51

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

Answer 51

F

Question 52

All infinite languages are regular.

Answer 52

F

Question 53

Every context free language is regular.

Answer 53

F

Question 54

Every regular language is a context free language.

Answer 54

T

Question 55

In BNFs, the terminal symbols are called tokens.

Answer 55

T

Question 56

Grammars and regular expressions are language generators.

Answer 56

T

Question 57

The results of parsing a program is a tree.

Answer 57

T

Question 58

EBNF allows defining language constructs that cannot be defined in BNF.

Answer 58

F

Question 59

A regular expression for an infinite language must have a Kleene closure or a positive closure.

Answer 59

T

Question 60

What is the term for the rules in a grammar that define how to modify strings by substitution?

Answer 60

Production

Question 61

What is a non-terminal alphabet.

Answer 61

It contains the symbols that do not occur in the string that is finally derived.

Question 62

What is the term for a sequence of strings created using a grammar where each string in the sequence is separated by =>?

Answer 62

Derivation.

Question 63

If each rule of a grammar has a single non-terminal on its left-hand side and a string containing at most one non-terminal on the right-hand, what kind of grammar is it?

Answer 63

right-linear grammar.

Question 64

What two kinds of grammars make up the regular grammars?

Answer 64

Right and left linear grammar.

Question 65

What kind of language is generated by a regular grammars?

Answer 65

Regular languages.

Question 66

What mathematical tryth is often used to prove languages non-regular?

Answer 66

Pumping lemma.

Question 67

What is a ' pumpable' substring?

Answer 67

A substring that can be repeated multiple times and still produce a string accepted by the language.

Question 68

If each rule of a grammar has a single nonterminal on its right-hand side, what kind of grammar is it?

Answer 68

Context free.

Question 69

How are nonterminal symbols written in BNF?

Answer 69

With words surrounded by angle-brackets.

Question 70

Give the formal definition of a grammar.

Answer 70

A grammar G is a 4-tuple G=(V,Σ,S,P) where: V is an alphabet, the nonterminal alphabet. Σ is another alphabet, the terminal alphabet, disjoint from V. S∈V is the start symbol. P is a finite set of productions, each of the form x→y, where x and y are strings over Σ∪V and x≠ɛ.

Question 71

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 aDFA, which is the regular languages.

Answer 71

F

Question 72

The size of the stack in a stack machine is limited to the cardinality of the stack alphabet.

Answer 72

F

Question 73

Stack machines make state transitions.

Answer 73

F

Question 74

When a stack machine starts, its stack contains just a special symbol, S.

Answer 74

T

Question 75

Stack machine are only nondeterministic.

Answer 75

F

Question 76

The transition function of a stack machine δ takes only one parameter.

Answer 76

F

Question 77

A stack machine can have a transition for the case when the state is empty.

Answer 77

F

Question 78

There is an equivalent stack machine for any finite atupmation.

Answer 78

T

Question 79

If M is a stack machine, L(M) is a CFG.

Answer 79

T

Question 80

If L is a CFG, there exists a stack machine that recognizes L.

Answer 80

T

Question 81

The intersection a CFL with a regular language is a CFL.

Answer 81

T

Question 82

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

Answer 82

F

Question 83

PDAs can be illustrated with state-transition diagrams.

Answer 83

F

Question 84

A PDA can be designed to accept a string by emptying its stack, by ending in an accept state, or by both.

Answer 84

T

Question 85

The DCFLs have the same closure properties as CFLs.

Answer 85

F

Question 86

The union of any two DCFLs is a DCFL.

Answer 86

T

Question 87

What is the operation that adds data to a stack?

Answer 87

Push

Question 88

How does a stack machine indicate that it has accepted the input string?

Answer 88

By leaving its stack empty.

Question 89

For an instantaneous description for a stack, (x,y), what are the x and y?

Answer 89

x= unused input; y= stack contents.

Question 90

What are some of the operations under which the CFLs are closed?

Answer 90

Union, Concatenation, and Kleene Star.

Question 91

Fow what operations are the CFLs not closed?

Answer 91

Complement and intersection.

Question 92

What does PDA stand for?

Answer 92

Push-down Automata.

Question 93

What is a deterministic context-free language?

Answer 93

A language L(M) for some DPDA M.

Question 94

What is the formal definition of a stack machine?

Answer 94

A stack machine M is a 4-tuple M=(Γ,Σ,S,δ) where: Γ is the stack alphabet. Σ is the input alphabet. S∈Γ is the intial stack symbol δ∈((Σ∪{ɛ})xΓ→P(Γ*)) is the transition function