CST - 2nd Examination

UM Tagum College
UM Visayan Campus, Tagum City, Davao del Norte

Telefax No.: (084) 655-9607 | Local 135
I. Multiple Choice. Choose the best answer that corresponds to the question. SHADE
the letter of the correct answer. If you think the answer is not found on the
choices, SHADE the letter that is closest to your answer.
1. Which of the following is true regarding the union of two languages L1 and L2 in the
theory of computation?
A. L1 U L2 contains only the common elements of L1 and L2.
B. L1 U L2 contains all strings that belong to either L1 or L2 or both.
C. L1 U L2 contains only the strings that belong to both L1 and L2.
D. L1 U L2 contains no elements.
2. The set of all strings over the alphabet ∑, including the empty string ε, is denoted by:
A. ∑∗
B. ∑+
C. ∑∗∗
D. ∑^+
3. Which of the following is true regarding the complement of the empty language?
A. It is the empty language itself.
B. It contains all possible strings over the alphabet.
C. It contains only the empty string.
D. It is undefined.
4. What type of strings can a DFA accept?

A. Strings that are palindromes
B. Strings that contain only lowercase letters
C. Strings that are formed by repeating a specific pattern
D. Strings that belong to its defined language
5. If L1 and L2 are regular languages, what is the language accepted by the DFA obtained by
concatenating DFAs accepting L1 and L2?
A. L1 U L2
UM Tagum College
Telefax No.: (084) 655-9607 | Local 135
B. L1 ∩ L2
C. L1 ∗ L2
D. L1L2
6. What is the key characteristic of a DFA?

A. It can remember an infinite amount of information
B. It can have multiple transitions for a symbol in the input alphabet
C. It can recognize non-regular languages.
D. It can be in only one state at any given time
7. A string over an alphabet is a finite set of sequence of symbols from that alphabet.
A. True
B. False
8. What is the language recognized by a DFA called?

A. Context-free language
B. Regular language
C. Context-sensitive language
D. Recursively enumerable language
9. In a DFA, which of the following determines whether a string is accepted or rejected?

A. Starting state
B. Accepting states
C. Transition function
D. Input alphabet
10. Which of the following statements is true about DFA?

A. DFA can recognize context-free languages.
B. DFA can recognize recursively enumerable languages.
C. DFA can recognize regular languages.
D. DFA can recognize context-sensitive languages.
UM Tagum College
Telefax No.: (084) 655-9607 | Local 135
11. Can every NFA (Nondeterministic Finite Automaton) be converted to an equivalent DFA?
A. Yes
B. No
C. Sometimes
D. Only for regular languages
12. Which of the following is true regarding DFA and NFA?

A. DFA can recognize more languages than NFA.
B. NFA can have multiple transitions for a symbol in the input alphabet.
C. DFA always requires more states than an equivalent NFA.
D. NFA is always faster in recognizing languages than DFA.
13. In a DFA, what is the significance of a dead state?

A. It represents a state where the automaton is trapped and cannot reach an
accepting state.
B. It signifies the starting state of the automaton.
C. It is the state where the automaton halts after processing the input string.
D. It indicates the final state of the automaton.
14. Can a DFA accept languages that contain infinitely many strings?
A. Yes, only if the language is regular.
B. Yes, if the language is context-free.
C. No, DFA can only accept finite languages.
D. No, DFA cannot accept any language with infinite strings.
15. A set that contains all possible strings over a given alphabet is known as:
A. Language
B. Grammar
C. Automaton
D. Transition
UM Tagum College
Telefax No.: (084) 655-9607 | Local 135
16. Which of the following statements about the empty set (Ø) is true?
A. It contains no elements.
B. It contains all possible elements.
C. It contains only one element.
D. It contains infinitely many elements.
17. What do you call a set of strings?

A. String
B. Language
C. Symbol
D. Regular language
18. Which of the following is NOT a basic set operation in the theory of computation?
A. Union
B. Intersection
C. Subtraction
D. Cardinality
19. What do you call the members of the alphabet?

A. String
B. Language
C. Symbol
D. Regular language
20. It refers to a sequence of symbols.

A. Set
B. String
C. Alphabet
D. Symbols
21. The language accepted by a DFA can be represented by:

A. A regular expression
UM Tagum College
Telefax No.: (084) 655-9607 | Local 135
B. A context-free grammar
C. A deterministic context-free grammar
D. A pushdown automaton
22. What is the result when the Kleene star operation is applied to a regular language
accepted by a DFA?
A. It generates a new regular language.
B. It generates a context-free language.
C. It generates an infinite language.
D. It generates a finite language.
23. Which element of the 5-tuple representation determines the next state of the DFA given
the current state and input symbol?
A. Set of states
B. Input alphabet
D. Start state
24. In the 5-tuple representation of a Deterministic Finite Automaton (DFA), what does the
first element represent?
A. Set of states
B. Input alphabet
D. Start state
25. In DFA, each state has exactly how many transitions for each symbol in the input
alphabet?
A. At most one
B. At least one
C. At most two
D. Exactly one
UM Tagum College
Telefax No.: (084) 655-9607 | Local 135
II. Base your answers on the diagrams indicated.
M1
26. Machine M1 accepts the string bbaaba.

A. True
B. False
27. Machine M1 accepts the string aabaab.

A. True
B. False
28. The inputs aabb in Machine M1 is accepted.

A. True
B. False
29. Machine M2 accepts the string babbaab.

A. True
B. False
30. Write the 5-tuple representation of Machine M1. (3 pts).

31. Using the set builder notation, write the language of machine M1? (3 pts)
UM Tagum College
Telefax No.: (084) 655-9607 | Local 135
M2
32. Write the 5-tuple representation of Machine M2. (3pts).
33. Using the set builder notation, write the language of machine M2. (3pts)
34. The formal description of a DFA M3 is ({q1, q2, q3, q4, q5}, {u,d}, 𝛿, q3, {q3}), where 𝛿 is
given by the following transition table:
u d
q1 q1 q2
q2 q1 q3
q3 q2 q4
q4 q3 q5
q5 q4 q5
Draw the state diagram of machine M3 based on the 5-tuple representation indicated. (3pts)
35. Draw the state diagram (5pts) for the given language below where: ∑= {0,1}. The
language {w | w ends with 00} with three states}.
UM Tagum College
Telefax No.: (084) 655-9607 | Local 135
36. The formal description of a DFA M4 is ({q1, q2, q3}, {a,b}, 𝛿, q1, {q2}) where 𝛿:
a b
q1 q2 q1
q2 q3 q3
q3 q2 q1
37. Draw the state diagram of machine M4 based on the 5-tuple representation indicated.
(3pts)
38. Draw the state diagram (5pts) for the given language below where: ∑= {0,1}. The
language {w | w has an odd number of a’s and ends with b}.

CST - 2nd Examination

Uploaded by

Copyright:

Available Formats

CST - 2nd Examination

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

CST - 2nd Examination

Uploaded by

Copyright:

Available Formats

UM Tagum College

UM Visayan Campus, Tagum City, Davao del Norte

4. What type of strings can a DFA accept?

6. What is the key characteristic of a DFA?

8. What is the language recognized by a DFA called?

9. In a DFA, which of the following determines whether a string is accepted or rejected?

10. Which of the following statements is true about DFA?

12. Which of the following is true regarding DFA and NFA?

13. In a DFA, what is the significance of a dead state?

17. What do you call a set of strings?

19. What do you call the members of the alphabet?

20. It refers to a sequence of symbols.

21. The language accepted by a DFA can be represented by:

II. Base your answers on the diagrams indicated.

26. Machine M1 accepts the string bbaaba.

27. Machine M1 accepts the string aabaab.

28. The inputs aabb in Machine M1 is accepted.

29. Machine M2 accepts the string babbaab.

30. Write the 5-tuple representation of Machine M1. (3 pts).

32. Write the 5-tuple representation of Machine M2. (3pts).

You might also like