Test 1

Question 1

What is an alphabet?

Answer 1

An alphabet is any non-empty finite set of symbols.

Question 2

What is a string?

Answer 2

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

Question 3

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

Answer 3

T

Question 4

What is a language?

Answer 4

A sequence over some fixed alphabet.

Question 5

In a DFA, an arrow points to one of the states, the unique start state; double circles mark any number of states as accepting states.

Answer 5

T

Question 6

If at an accepting state, we say that the machine…?

Answer 6

accepts the string.

Question 7

What is it called when a string can’t reach the accepting state?

Answer 7

it is rejected.

Question 8

What is the 5-tuple in symbol form?

Answer 8

M=(Q,Σ,δ,qsub0,F)

M = Q, Epsilon, Delta, q sub 0, F

Question 9

The complement of a machine language is the reverse of the accepting states.

Answer 9

T

Question 10

If “L” is any regular language, “L Complement” is also a regular language?

Answer 10

T

Question 11

What are closed under complement?

Answer 11

Regular languages.

Question 12

What is the product construction theorem?

Answer 12

If L1 and L2 are any regular languages, L1 intersect L2 is also a regular language.

Question 13

If L1 and L2 are any regular languages, L1 union L2 is not a regular language.

Answer 13

F

Question 14

For intersections, the new DFA accept when both the original DFAs accept.

Answer 14

T

Question 15

Four unions, the new DFA accepts when?

Answer 15

Either or both of the original DFAs accept.

Question 16

Whenever you prove something, you have to exercise judgment about how much to give.

Answer 16

T

Question 17

The empty set is a legal alphabet.

Answer 17

T

Question 18

The empty set {} = {e}.

Answer 18

F

Question 19

The Kleene close of an alphabet is written how, and is the set of what?

Answer 19

E*(epsilon), all empty strings over E (epsilon).

Question 20

Any and EVERY state transition diagram is a DFA.

Answer 20

F

Question 21

What should be shown to make state transition diagrams fully specified?

Answer 21

Exactly one transition from every state.

Question 22

“Q” often represents what?

Answer 22

A finite set of states.

Question 23

Epsilon often represents what?

Answer 23

An alphabet.

Question 24

Delta represents what?

Answer 24

(Q cross Epsilon)

Question 25

What symbol represents the start state?

Answer 25

(q sub 0) is in the set of Q

Question 26

What is the final part of the DFA F?

Answer 26

F is a subset of Q identifying the set of accepting states

Question 27

What is a regular language?

Answer 27

A language that can be recognized by a DFA.

Question 28

Regular languages are closed under intersections.

Answer 28

T

Question 29

Regular languages are not closed under union.

Answer 29

F

Question 30

Each move in a state transition diagram is called what?

Answer 30

state transition.

Question 31

What symbol represents the start state in a state transition diagram?

Answer 31

Arrow.

Question 32

How many strings are in {e}?

Answer 32

1