KOFORIDUA TECHNICAL UNIVERSITY
SCHOOL OF APPLIED SCIENCE AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE
BTECH COMPUTER SCIENCE & NETWORKING 1 2023/2024
TUTORIAL 1: 2023/24 ACADEMIC YEAR
Course Title: Theory of Computation & Formal Languages Course Code: CSD 108
SECTION A: MULTIPLE CHOICE QUESTIONS
1. Given the language L = ab, aa, baa , which of the following strings are in L
1) abaabaaabaa 2) aaaabaaaa 3) baaaaabaaaab 4) baaaaabaa
( A ) 1, 2 and 3 ( B) 2, 3 and 4 ( C ) 1, 2 and 4
2. Suppose L1 = 10,1 and L2 = 011,11 ; How many distinct elements are there in L = L1 L2
a) 4 b) 3 c) 2 d) None of these
3. The following DFA accepts the set of all strings over 0,1
a) Begin either with 0 or 1 b) End with 0
c) End with 00 d) Contain the substring 00 .
1
4. Consider the machine M shown below L ( M )
a) L ( M ) = words starting with aa or bb b) L(M)= words ending with aa or bb
c) L(M)= words containing aa or bb as a sub word , d) None of these
5. Consider the transition diagram of a DFA as given below
2
Which of them should be the final state (s) of the DFA if it should accept strings starting with “a”
and ending with “b”
a) q 0 b) q1 c) q 0 , q1 d) q 3
6. Consider the machine M
The language recognized by M is:
( A) w a,b / every a in w is followed by exactly two b's
( B) w a,b / every a in w is followed by at least two b
( C) w a,b w contains the substring "abb"
( D) w a,b w does not contain "aa" as a substring
3
7. Consider the finite automaton in the following figure
What is the set of reachable states for the input string 0011?
( A ) q 0 , q1 , q 2 ( B ) q 0 , q1 ( C ) q 0 , q1 , q 2 , q3 ( D ) q3
8. Consider the following two finite automata. M1 accepts L1 and M 2 accepts L2 . Which
one of the following is true?
4
a) L1 = L 2 b) L1 L 2 c) L1 L2 = d) L1 L2 L1
9. Consider the Non-Deterministic Finite automaton (NDFA) shown in the figure below
State X is the starting state of the automaton. Let the language accepted by the NFA with
Y as the only accepting state be L1 . Similarly, let the language accepted by the NFA with
Z as the only accepting state be L2 . Which of the following statements about L1 and L2
is true?
( A ) L1 = L2 ( B ) L1 L 2 ( C ) L1 L2 ( D ) None of the above
10. If an NDFA accepting L is denoted by ( Q, S, d, q 0 , F ) the equivalent DFA is denoted
M= ( Q, , , q0 , F ) . Which of the following is true?
a) Q 2Q b) q0 = q 0
c) F is the set containing all elements of F d) all of the above .
11. Which of the following is false?
a) The languages accepted by FAs are regular languages
b) Every DFA is an NFA
c) There are some NFAs for which no DFA can be constructed
5
d) If L is accepted by an NFA with transition then L is accepted by an NFA without transition
12. If L is a regular language over = a, b , which one of the following languages is NOT
regular?
a) [Link] = xy x L, yR L
b) Suffix(L) = y x such that xy L
c) Prefix ( L ) = x
y such that xy L
d) ww R w L
13. Given the following two languages:
L1 = u, w, w R v u, v, w a, b
+
= u, w, w v u, v, w a, b , u v
R +
L2
Which of the following is correct?
a) L1 is regular language and L2 is not regular language
b) L1 is not regular language and L2 is regular language
c) Both L1 and L2 are regular languages.
d) Both L1 and L2 are not regular languages.
( )
14. Let S and T be languages over = a,b represented by the regular expressions a + b
and ( a + b ) , respectively. Which of the following is true?
(A) S T ( B) T S ( C ) S=T ( D) S T=
15. Consider the languages L1 = and L2 = a . Which one of the following represents
L1L2 L1
( A ) ( B) (C) a ( D ) , a
16. Finite state machine can recognize language generated by …………
a) Only context free grammar
b) Only context sensitive grammar
6
c) Only regular grammar
d) any unambiguous grammar.
17. Let = a, b and the language L= aa, bb . Then, the complement of L
a) , a, b, ab, ba w a, b
w 3
b) a, b, ab, ba w a, b w>3
c) w a, b w>3 a, b, ab, ba
d) , a, b, ab, ba w a, b w 3
18. If G is a grammar with productions S → SaS aSb bSa SS where S is the start variable,
which one of the following strings is not generated by G?
( A ) abab ( B) aaab
( C ) abba ( D ) babba
19. Two finite-state machines are said to be equivalent if they
a. Have the same number of edges
b. Have the same number of states
c. Recognize the same set of tokens
d. Have the same number of states and edges
20. Which of the following statements are true?
i) The complement of a language is always regular
ii) The intersection of regular languages is regular
iii) The complement of a regular language is regular
a) i) and ii) b) ii) and iii) only c) i) and iii) only d) All of the above
7
21. The set +
a. Is the infinite set of all possible strings of all possible lengths over excluding
b. Is the infinite set of all possible strings of all possible lengths over including
c. Is the finite set of all possible strings of all possible lengths over excluding
d. Is the finite set of all possible strings of all possible lengths over including
22. A language is a subset of for some alphabet .
a. It cannot be finite nor infinite
b. It cannot be infinite but finite
c. It can be finite or infinite.
d. It cannot be finite but infinite.
23. Non-Deterministic Finite Automaton (NDFA) permits empty string transitions.
a. False
b. True.
24. An NDFA accepts a string,
a. If at least one of all possible transitions ends in a final state.
b. If at most one of all possible transitions ends in a final state.
c. If exactly one transition ends in a final state.
d. If no transition ends in a final state.
25. Given a regular expression defined as ( 0 + 10 ) ,
it corresponding regular set can be
determined as
a. L = , 0, 1, 01
b. L = 1, 01, 10, 010, 0010,
c. L = 0, 1, 10, 100, 1000, 10000,
d. L = 1, 10, 100, 1000, 10000,
26. If a context-free grammar G has more than one derivation tree for some string w L ( G ) ,
it is called:
a. An ambiguous grammar
b. An unambiguous grammar.
8
c. A grammar
d. A non-grammar
27. Pumping lemma is used to check whether a(n)
a. Alphabet
b. String
c. Symbol
d. Grammar
Is context-free or not.
28. In the context of Push Down Automaton ……..can remember a finite amount of
information,
a. DFA
b. NDFA
c. PDA
d. NPDA
29. A pushdown automaton has………components
a. 3
b. 4
c. 2
d. 1
9
Considering the table above, answer questions 10 to 11
30. A stack does ……. operation (s)
a. 3
b. 4
c. 2
d. 1
31. A PDA may or may not read an input symbol,
a. But it has to read the top of the stack in every transition
b. But it has to read the bottom of the stack in every transition
c. But it has to read the top of the stack in just one transition.
d. But it has to read the bottom of the stack in just one transition.
32. A Push Down Automaton can be formally described as a ……. -tuple.
a. 4
b. 5
c. 6
d. 7
33. For a PDA ( Q, , S , , q0 , I , F ) , the language accepted by the set of final states F for any
input stack string is x
a.
L ( PDA) = w ( q0 , w, I ) ( q0 , , ) , q0 F
b.
L ( PDA) = w ( q0 , w, I ) ( q, , x ) , q F
c.
L ( PDA) = w ( q0 , w, I ) ( q, , ) , q F
d.
L ( PDA) = w ( q0 , w, I ) ( q, , ) , q0 F
34. A Mealy Machine is an FSM whose output depends on
a. The present state as well as the present input.
b. The past state as well as the present input
c. The present state as well as the past input.
d. The past state as well as the past input.
35. A Moore Machine is an FSM whose outputs depend on
a. Only the past state.
b. Only the present state
10
c. The present state and past state
d. None of the states.
36. A Moore Machine can be described by ……. tuple
a.
4
b.
5
c.
6
d.
7
37. In a string of length n, how many proper prefixes can be generated?
a. 2 n
b. n
c. n ( n + 1) / 2
d. n − 1
State whether the following statements 18 – 20 are true or false.
38. In a grammar G = (VN , , P, S ) , VN and are finite but P can be infinite
39. If a grammar G has three productions, i.e., S → AA, A → aa, A → bb , then L ( G ) is
finite.
40. If a grammar G has productions S → aS bS a , then L ( G ) = the set of all strings over
a, b ending in a
11