Programming Languages (Quiz 1-4) Flashcards
The mathematical models are called machines and the types of inputs on which they operate successfully call the language of the machine.
True
A finite set of fundamental units out of which we build structures is called
Alphabet
Λ is a word with no letter.
True
The language which has no words is denoted by
ɸ (phi)
The set of words is always finite but alphabets can be infinite.
False. (Set of words is infinite, the alphabet is finite)
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 Λ.
False. Σ*, not Σ+.
Which of the following is true for Σ = {x}? (What will the Kleene-Star contain?)
It will contain Λ and finite sequences of letters in the alphabet. Σ * = { Λ, x, xx, xxx, …} .
If S = {xx, xxx},
and xxxxxxx Є S*,
then which of the following is the factor of S:
xx|xx|xxx and xx|xxx|xx.
The Kleene closure of a language S always produces an infinite language unless S = ɸ or S = {Λ}.
True
If S = {a, b, Λ } than S+ = { Λ, a, b, aa, bb, ab, ba, …}.
True, Kleene-Star contains Λ while Positive Closure does not.
A recursive definition is characteristically a three-step process.
True.
- Specify the basic words
- Rules for constructing new words from ones already known
- Declare that no word except those constructed by following rules 1 and 2 are in the language
∑ = {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 = ?
x*
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 = ?
X odd
language(ab) ≠ language(ab)*
True.
(ab) = ab, aabb, aaabbb, …
(ab)* = ab, abab, ababab, …
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)
T = language((a+c)b*) T = {a, c, ab, cb, abb, cbb, abbb, cbbb, …}
Regular expression (a+b)a(a+b) + b* can be simplified into what?
(a+b)*
(a+b)a(a+b)a(a+b)* and babab* are equivalent regular expressions which accept all words that have exact two a’s.
False. First regular expression contains AT LEAST 2 a’s, while the second expression contains EXACTLY 2 a’s.
Let S = {a, bb} and T = {a, ab} then ST =?
ST = {aa, aab, bba, bbab}
For all regular expressions, there is some language associated with it.
True. Regular expressions guide you to accepted words in the language.
The regular expression must be infinite if the language defined is infinite.
False, Regular expression must be infinite.
There is not necessarily a unique FA that accepts a given language.
True
Every language that can be accepted by an FA can be defined by a regular expression.
True
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.
Crashes
Every finite automaton is a transition graph. But not every TG satisfies the definition of an FA.
True
Every language that can be defined by FA can also be defined by TG.
True
Every language that can be defined by a TG may or may not be defined by RE.
False, if it’s defined by TG then it can also be defined by RE.
In the case of r1+r2, the resultant final state will be only those where x and y both are final states.
False, it’s either-or.
For the language defined by r*, the start state must be the final state.
True, cover the case for Λ.
Every FA is also NFA.
True, FA is part of TG, and TG is part of NFA, and FA is part of NFA.
Every TG is also NFA.
True
In the Mealy machine, the output string has the same number of characters as the input string has letters.
True, a/0, b/1, …
Moore machine and the mealy machine does not define a language by accepting and rejecting input.
True
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.
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)
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.
True
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.
True
If there is an FA that accepts the language defined by r, then there is an FA that accepts the language defined by r*.
True