CIT342 List of Questions
Q1 A grammar G is ambiguous if there exists some string w �?? L(G) for which �?��?��?�..
there are two or more distinct derivation trees
there are two or more distinct leftmost derivations
there are two or more distinct rightmost derivations.
All of the options
Q2 The reduction u �??v is called a �?��?��?��?��?��?�..
direct production
direct variable
direct function
None of the Options
Q3 The pumping lemma is based on the �?��?��?��?��?�. principle and it can be used to prove that an infinite language is not regular.
pigeon hose
pigeon pole
pigeon hole
None of the Options
Q4 The Pumping Lemma says that: �?��?��?��?�.
If an infinite language is regular, it can be defined by a DFA.
The DFA has some finite number of states (say, n).
Since the language is infinite, some strings of the language must have length > n.
All of the options
Q5 A regular language is given in a standard representation if it is specified by one of:
A regular expression.
A regular notion.
A regular grammar.
A finite automaton (DFA or NFA).
Q6 Let L1 and L2 be languages on the same alphabet. The right quotient of L1 with L2 is L1/L2 = �?��?��?��?��?��?��?��?��?�
{w: wx �? L1 and x �? L2}
{w: x �? L1 and x �? L2}
{w: wx �? L1 and xw �? L2}
None of the Options
Q7 A language is recursively enumerable if there exists a �?��?��?��?��?�. that accepts every string of the language, and does not accept strings that are not in the language.
Turing Text
Turing Codes
Turing machines
None of the Options
Q8 Basically, unrestricted grammars are equivalent to �?��?��?��?��?��?�….
Turing Text
Turing Codes
Turing machines
None of the Options
Q9 �?��?��?��?��?��?��?��?�. is a set of rules for forming strings in a formal language.
formal text
formal grammar
formal character
None of the Options
Q10 The Pumping Lemma says that: �?��?��?��?�.
If an infinite language is regular, it can be defined by a DFA.
The DFA has some finite number of states (say, n).
Since the language is infinite, some strings of the language must have length > n.
All of the options
Q11 A string is a �?��?��?��?��?�.. sequence of symbols that are chosen from a set or alphabet
character
finite
data
None of the Options
Q12 What value will the string function: length(“hello world”) return?
11
12
10
None of the Options
Q13 A string s is said to be a substring or factor of t if there exist (possibly empty) strings u and v such that �?��?��?��?�….
t = u
t = usv
t = us
t = sv
Q14 If Σ = {a, b, �?�, z}, s = bear, and t = hug, then concatenation of ts will result to �?��?��?��?��?��?�
hug_bear
hugbear
hug+bear
hug*bear
Q15 If Σ = {a, b, �?�, z}, s = bear, and t = hug, then concatenation of st will result to �?��?��?��?��?��?�
bear_hug
bearhug
bear+hug
bear*hug
Q16 L1 – L2 implies that
Strings in L1 that greater than L2
Strings in L1 that are less than L2
Strings in L1 that are not in L2
None of the Options
Q17 L1 �?� L2 implies that
Strings in both L1 and L2
Strings in either L1 or L2
Strings in neither L1 or L2
None of the Options
Q18 L1 �? L2 implies that
Strings in both L1 and L2
Strings in either L1 or L2
Strings in neither L1 or L2
None of the Options
Q19 A set is �?��?��?��?��?��?�.. under an operation if, whenever the operation is applied to members of the set, the result is also a member of the set.
opened
crossed
closed
fitted
Q20 A �?��?��?��?��?��?��?�… grammar is either a right-linear grammar or a left-linear grammar
regular
standard
static
perfect
Q21 The grammar generates a language whose strings are of the form aﬨ bﬨ cannot be recognized by a
DFCA
DFA
DFAD
DFB
Q22 A right-linear grammar, every production of the grammar must have one of the two forms V �?? T*V or
V �?? VT*
V �?? V*
V �?? T*
T �?? VT*
Q23 There are three other types of languages in Chomsky hierarchy: context-free languages, context sensitive languages and �?��?��?��?��?��?��?��?��?�..
phrase structure languages.
parsing structure languages.
Logic structure languages.
context structure languages.
Q24 In a left-linear grammar, all productions have one of the two forms: V �?? VT* or
V �?? VT*
V �?? V*
V �?? T*
T �?? VT*
Q25 A grammar G is a quadruple Where G = (V, T, S, P) then
P is a finite set of variables
P is a a distinguished element of V called the start symbol
P is a finite set of (meta)symbols, or variables.
P is a finite set of productions
Q26 A grammar G is a quadruple Where G = (V, T, S, P) then
T is a finite set of terminal symbols.
T is a a distinguished element of V called the start symbol
T is a finite set of (meta)symbols, or variables.
T is a finite set of productions..
Q27 A grammar G is a quadruple Where G = (V, T, S, P) then
V is a finite set of productions
V is a a distinguished element of V called the start symbol
V is a finite set of (meta)symbols, or variables.
V is a finite set of terminal symbols..
Q28 In Ada, an identifier consists of a �?��?��?��?��?�.. followed by any number of letters, digits, and underlines.
digit
letter
points
data
Q29 DFA is a quintuple in which M = (Q, �?? , δ, q0, F)
q0 is a finite set of symbols, the input alphabet
q0 is transition function,,
q0 is a set of final states
q0 �? Q is the initial state,
Q30 DFA is a quintuple in which M = (Q, �?? , δ, q0, F)
�?? is a finite set of symbols, the input alphabet,
�?? is the initial state,
�?? is a transition function,
�?? is the initial state
Q31 DFA is a quintuple in which M = (Q, �?? , δ, q0, F)
Q is a finite set of symbols, the input alphabet
Q is the initial state,
Q isa set of final states
Q is a finite set of states
Q32 In a DFA diagram, Arcs between states represent �?��?��?��?��?�
state transitions.
state circles.
state spots.
state points.
Q33 A DFA is drawn as a graph, with each state represented by a �?��?��?��?��?��?��?�
Dot
Point
Circle
Spot
Q34 The acronym DFA stands for �?��?��?��?��?��?��?�.
Deterministic Form Acceptors/Automata
Defined Finite Acceptors/Automata
Deterministic Finite Acceptors/Automata
Defined Form Acceptors/Automata
Q35 If Σ = {a, b, �?�, z}, s = bear, and t = hug, then concatenation of st will result to �?��?��?��?��?��?�
bear_hug
bearhug
bear+hug
bear*hug
Q36 The alphabet of a string is a list of all of the letters that occur in a particular string. If s is a string, its alphabet is denoted by
Alph(s*s)
Alph(s&s)
Alph(s, s)
Alph(s)
Q37 �?��?��?��?��?��?��?�. grammar is a grammar in which the left-hand side of each production rule consists of only a single nonterminal symbol.
analystic
context-free
regular
complex
Q38 Noam Chomsky first formalized generative grammars in �?��?��?��?��?�…, he classified them into types now known as the Chomsky hierarchy.
1956
1965
1945
1966
Q39 �?��?��?��?��?�.. returns the length of a string (not counting any terminator characters or any of the string’s internal structural information) and does not modify the string.
length(string)
lengths(string)
length(strings)
leng(string)
Q40 In formal languages, which are used in mathematical logic and theoretical computer science, �?��?��?��?��?��?�. is a finite sequence of symbols that are chosen from a set or alphabet
string
symbol
letter
character
Q41 �?��?��?��?��?��?�. are approximations to real numbers are equivalent and can be put in one-to-one correspondence with the integers.
Notational numbers
Rational numbers
Irrational numbers
None of the Options
Q42 �?��?��?��?��?�. an encoded Turing machine on its input tape followed by normal Turing machine input data on that same input tape.
UTM
TTM
ATM
None of the Options
Q43 UTM is an acronym for �?��?��?��?��?��?��?�
Universal Turbo Machine
Unique Turing Machine
Universal Turing Model
Universal Turing Machine
Q44 A language is �?��?��?��?��?��?�…, if there is a TM which will always stop
undecidable
acceptable
decidable
None of the Options
Q45 The Halting Problem says that no computer program can determine if ALL computer programs will halt or not halt on �?��?��?��?��?��?�…
ALL elements
ALL inputs
ALL figures
ALL records
Q46 We say that a grammar is context-sensitive (or type 1) if the left hand side of a production is at least as long as the right hand side. That is for each a �??b �?? P we have�?��?��?��?��?�.
|a| �?� |b |
|a|�?� |b |
|a| �?� |b |
|a| ± |b |
Q47 Finding a derivation (or a derivation tree) for that string is called �?��?��?��?��?�..
Sorting
Parting
Loading
Parsing
Q48 The �?��?��?��?��?��?��?�… search parsing is one that allow us to parse a string w, generate all strings in L and see if w is among them.
partial
absolute
close
exhaustive
Q49 For any context-free grammar G, the algorithms for parsing strings is �?��?��?��?��?��?��?��?��?�… in time proportional to the cube of |w|.
w �?? L(G)
w = L(G)
w �?� L(G)
None of the Options
Q50 FSA is an acronym for �?��?��?��?��?��?�..
first-stage automaton
finite-state automaton
first-state automaton
finite-stage automaton
Q51 NPDA is a 7-tuple of M = (Q, �?? , �?�, δ , q0, z, F) where �?? is �?��?��?��?��?��?�.
�?� is a the input alphabet
�?� is a finite set of states,
�?� is the stack alphabet
�?� is a transition function,
Q52 NPDA is a 7-tuple of M = (Q, �?? , �?�, δ , q0, z, F) where �?? is �?��?��?��?��?��?�.
δ is a the input alphabet
δ is a finite set of states,
δ is the initial state,
δ is a transition function
Q53 NPDA is a 7-tuple of M = (Q, �?? , �?�, δ , q0, z, F) where �?? is �?��?��?��?��?��?�.
�?? is a the input alphabet
�?? is a finite set of states,
�?? is the initial state,
�?? is a transition function,
Q54 NPDA is a 7-tuple of M = (Q, �?? , �?�, δ , q0, z, F) where Q is �?��?��?��?��?��?�.
Q is the stack alphabet,
Q is a finite set of states,
Q is the initial state,
Q is a transition function,
Q55 NPDA is an acronym for �?��?��?��?��?��?�
deter pushdown automaton
deterministed pushdown automaton
Nondeterministic pushdown automaton
determining pushdown automaton
Q56 DPDA is an acronym for �?��?��?��?��?��?�
deter pushdown automaton
deterministed pushdown automaton
deterministic pushdown automaton
determining pushdown automaton
Q57 A �?��?��?��?��?��?��?��?��?��?� PDA (NPDA) is one in which we may have to choose among several paths for an input string.
deterministic
nondeterministic
Sub-deterministic
None of the Options
Q58 A �?��?��?��?��?��?��?��?�. PDA (DPDA) is one in which every input string has a unique path through the machine.
Sub-deterministic
Nondeterministic
deterministic
None of the Options
Q59 A �?��?��?��?�.. production is one of the form A �?? B where both A and B are nonterminals.
unit
unique
union
universal
Q60 A grammar is in �?��?��?��?��?��?��?�… if all productions are of the form: A�?? ax where a is a terminal and x �? V*.
Chomsky Notation Form
Greibach Notation Form
Chomsky Normal Form
Greibach Normal Form
Q61 �?��?��?��?��?��?�. are approximations to real numbers are equivalent and can be put in one-to-one correspondence with the integers.
Notational numbers
Rational numbers
Irrational numbers
None of the Options
Q62 �?��?��?��?��?�. an encoded Turing machine on its input tape followed by normal Turing machine input data on that same input tape.
UTM
TTM
ATM
None of the Options
Q63 UTM is an acronym for �?��?��?��?��?��?��?�
Universal Turbo Machine
Unique Turing Machine
Universal Turing Model
Universal Turing Machine
Q64 A language is �?��?��?��?��?��?�…, if there is a TM which will always stop
undecidable
acceptable
decidable
None of the Options
Q65 The Halting Problem says that no computer program can determine if ALL computer programs will halt or not halt on �?��?��?��?��?��?�…
ALL elements
ALL inputs
ALL figures
ALL records
Q66 We say that a grammar is context-sensitive (or type 1) if the left hand side of a production is at least as long as the right hand side. That is for each a �??b �?? P we have�?��?��?��?��?�.
|a| �?� |b |
|a|�?� |b |
|a| �?� |b |
|a| ± |b |
Q67 A language is recursively enumerable if there exists a �?��?��?��?��?�. that accepts every string of the language, and does not accept strings that are not in the language.
Turing Text
Turing Codes
Turing machines
None of the Options
Q68 Basically, unrestricted grammars are equivalent to �?��?��?��?��?��?�….
Turing Text
Turing Codes
Turing machines
None of the Options
Q69 �?��?��?��?��?��?��?��?�. is a set of rules for forming strings in a formal language.
formal text
formal grammar
formal character
None of the Options
Q70 �?��?��?��?��?��?�… functions are used to manipulate a string or change or edit the contents of a string
String
Object
Text
character
Q71 A string is a �?��?��?��?��?�.. sequence of symbols that are chosen from a set or alphabet
character
finite
data
None of the Options
Q72 What value will the string function: length(“hello world”) return?
11
12
10
None of the Options
Q73 A string s is said to be a substring or factor of t if there exist (possibly empty) strings u and v such that �?��?��?��?�….
t = u
t = usv
t = us
t = sv
Q74 If Σ = {a, b, �?�, z}, s = bear, and t = hug, then concatenation of ts will result to �?��?��?��?��?��?�
hug_bear
hugbear
hug+bear
hug*bear
Q75 If Σ = {a, b, �?�, z}, s = bear, and t = hug, then concatenation of st will result to �?��?��?��?��?��?�
bear_hug
bearhug
bear+hug
bear*hug
Q76 The alphabet of a string is a list of all of the letters that occur in a particular string. If s is a string, its alphabet is denoted by
Alph(s*s)
Alph(s&s)
Alph(s, s)
Alph(s)
Q77 �?��?��?��?��?��?��?�. grammar is a grammar in which the left-hand side of each production rule consists of only a single nonterminal symbol.
analystic
context-free
regular
complex
Q78 Noam Chomsky first formalized generative grammars in �?��?��?��?��?�…, he classified them into types now known as the Chomsky hierarchy.
1956
1965
1945
1966
Q79 �?��?��?��?��?�.. returns the length of a string (not counting any terminator characters or any of the string’s internal structural information) and does not modify the string.
length(string)
lengths(string)
length(strings)
leng(string)
Q80 In formal languages, which are used in mathematical logic and theoretical computer science, �?��?��?��?��?��?�. is a finite sequence of symbols that are chosen from a set or alphabet
string
symbol
letter
character
FOR YOUR COURSE TMA SOLUTIONS as well as PAST QUESTIONS AND ANSWERS FOR EXAMS CONTACT 08039407882 on whatsapp.
