Programming Languages (Quiz 1-4)

Question 1

The mathematical models are called machines and the types of inputs on which they operate successfully call the language of the machine.

Answer 1

True

Question 2

A finite set of fundamental units out of which we build structures is called

Answer 2

Alphabet

Question 3

Λ is a word with no letter.

Answer 3

True

Question 4

The language which has no words is denoted by

Answer 4

ɸ (phi)

Question 5

The set of words is always finite but alphabets can be infinite.

Answer 5

False. (Set of words is infinite, the alphabet is finite)

Question 6

Given an alphabet Σ, the closure of Σ (or Kleene star), denoted by Σ+, is the language containing all words made up of finite sequences of letters from Σ, including the empty string Λ.

Answer 6

False. Σ*, not Σ+.

Question 7

Which of the following is true for Σ = {x}? (What will the Kleene-Star contain?)

Answer 7

It will contain Λ and finite sequences of letters in the alphabet. Σ * = { Λ, x, xx, xxx, …} .

Question 8

If S = {xx, xxx},

and xxxxxxx Є S*,

then which of the following is the factor of S:

Answer 8

xx|xx|xxx and xx|xxx|xx.

Question 9

The Kleene closure of a language S always produces an infinite language unless S = ɸ or S = {Λ}.

Answer 9

True

Question 10

If S = {a, b, Λ } than S+ = { Λ, a, b, aa, bb, ab, ba, …}.

Answer 10

True, Kleene-Star contains Λ while Positive Closure does not.

Question 11

A recursive definition is characteristically a three-step process.

Answer 11

True.

1. Specify the basic words
2. Rules for constructing new words from ones already known
3. Declare that no word except those constructed by following rules 1 and 2 are in the language

Question 12

∑ = {x}

Rule 1 Λ is in L1.

Rule 2 if w is any word in L1, then xw is also in L1.

What is this L1 = ?

Answer 12

x*

Question 13

Rule 1 x is in L1.

Rule 2 if w is any word in L1, then xxw is also in L1.

What is this L1 = ?

Answer 13

X odd

Question 14

language(ab) ≠ language(ab)*

Answer 14

True.
(ab) = ab, aabb, aaabbb, …
(ab)* = ab, abab, ababab, …

Question 15

Consider the language T (language whose words are constructed from either a or c followed by some b’s) defined over the alphabet Σ whereas Σ = {a, b, c}

Which of the following is true for language T? (define language T)

Answer 15

T = language((a+c)b*) 
T = {a, c, ab, cb, abb, cbb, abbb, cbbb, …}

Question 16

Regular expression (a+b)a(a+b) + b* can be simplified into what?

Answer 16

(a+b)*

Question 17

(a+b)a(a+b)a(a+b)* and babab* are equivalent regular expressions which accept all words that have exact two a’s.

Answer 17

False. First regular expression contains AT LEAST 2 a’s, while the second expression contains EXACTLY 2 a’s.

Question 18

Let S = {a, bb} and T = {a, ab} then ST =?

Answer 18

ST = {aa, aab, bba, bbab}

Question 19

For all regular expressions, there is some language associated with it.

Answer 19

True. Regular expressions guide you to accepted words in the language.

Question 20

The regular expression must be infinite if the language defined is infinite.

Answer 20

False, Regular expression must be infinite.

Question 21

There is not necessarily a unique FA that accepts a given language.

Answer 21

True

Question 22

Every language that can be accepted by an FA can be defined by a regular expression.

Answer 22

True

Question 23

When an input that has not been completely read reached a state (final or otherwise) that it cannot leave because there is no outgoing edge that it may follow. The input or the machine __________at that stage.

Answer 23

Crashes

Question 24

Every finite automaton is a transition graph. But not every TG satisfies the definition of an FA.

Answer 24

True

Question 25

Every language that can be defined by FA can also be defined by TG.

Answer 25

True

Question 26

Every language that can be defined by a TG may or may not be defined by RE.

Answer 26

False, if it’s defined by TG then it can also be defined by RE.

Question 27

In the case of r1+r2, the resultant final state will be only those where x and y both are final states.

Answer 27

False, it’s either-or.

Question 28

For the language defined by r*, the start state must be the final state.

Answer 28

True, cover the case for Λ.

Question 29

Every FA is also NFA.

Answer 29

True, FA is part of TG, and TG is part of NFA, and FA is part of NFA.

Question 30

Every TG is also NFA.

Answer 30

True

Question 31

In the Mealy machine, the output string has the same number of characters as the input string has letters.

Answer 31

True, a/0, b/1, …

Question 32

Moore machine and the mealy machine does not define a language by accepting and rejecting input.

Answer 32

True

Question 33

If L is a language over the alphabet S, the complement of L, written L’ is the language of all strings of letters from S that are words in L.

Answer 33

False, the complement of L, L’, is the language of all strings of letters from S that are NOT words in L. (Still contains letters from the same alphabet, just not the words in L)

Question 34

If there is an FA that accepts the language defined by r1 and an FA that accepts the language defined by r2, then there is an FA that accepts the language r1+r2.

Answer 34

True

Question 35

If there is an FA that accepts the language defined by r1 and an FA that accepts the language defined by r2, then there is an FA that accepts the language defined by their concatenation r1r2.

Answer 35

True

Question 36

If there is an FA that accepts the language defined by r, then there is an FA that accepts the language defined by r*.

Answer 36

True