Scribd
Upload
1K views4 pages

Final Exam For Finite Automata

This document contains 20 multiple choice questions and 5 short answer questions about deterministic finite automata (DFAs). The questions cover topics such as what DFA stands for, the components of a finite state machine, transition functions, regular expressions, accepting conditions of DFAs, representations of DFAs as transition graphs or tables, languages accepted by DFAs and PDAs, and examples of DFAs for specific languages.

Uploaded by

Salih Anwar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
1K views4 pages

Final Exam For Finite Automata

This document contains 20 multiple choice questions and 5 short answer questions about deterministic finite automata (DFAs). The questions cover topics such as what DFA stands for, the components of a finite state machine, transition functions, regular expressions, accepting conditions of DFAs, representations of DFAs as transition graphs or tables, languages accepted by DFAs and PDAs, and examples of DFAs for specific languages.

Uploaded by

Salih Anwar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

1. What does DFA stand for?

A. Deterministic final automata


B. Determined finite automata
C. Deterministic finite automata
D. Deterministic finite automatic
2. There are ________ tuples in finite state machine.
A. 4 B. 5 C. 6 D. unlimited
3. Transition function maps.
a) Σ * Q -> Σ B. Q * Q -> Σ C. Σ * Σ -> Q D. Q * Σ -> Q
4. Regular expression for all strings starts with ab and ends with bba is.
A. aba*b*bba B. ab(ab)*bba C. ab(a+b)*bba D. All of the mentioned
5. Which of the following is not a part of 5-tuple finite automata?
a) Input alphabet B. Transition function C. Initial State D. Output Alphabet
6. A Language for DFA is a________
A. Regular Language B. Non-Regular Language C. May be Regular D. None
7. A DFA can be represented in the following format
a) Transition graph
b) Transition Table
c) all
8. What the following DFA accepts?

a) x is a string such that it ends with ‘101’


b) x is a string such that it ends with ‘01’
c) x is a string such that it has odd 1’s and even 0’s
d) x is a strings such that it has starting and ending character as 1
9. What does the following figure most correctly represents?

a) Final state with loop x


b) Transitional state with loop x
c) Initial state as well as final state with loop x
d) Insufficient Data
10. Which of the following will the given DFA won’t accept?

a) ε
b) 11010
c) 10001010
d) String of letter count 11
11. A push down automaton employs ________ data structure.
a) Queue
b) Linked List
c) Hash Table
d) Stack
12. Push down automata accepts _________ languages.
a) Regular Language
b) Non-Regular Language
c) May be Regular
d) context free language
13. Which of the following will not be accepted by the following DFA?

a) ababaabaa
b) abbbaa
c) abbbaabb
d) abbaabbaa
II. Short answer

1. Draw a DFA for the language accepting strings ending with ‘abb’ over input alphabets ∑
= {a, b}
2. Draw a DFA for the language accepting strings ending with ‘0’ over input alphabets
∑={0, 1} ? 

3. Convert the following Non-Deterministic Finite Automata (NFA) to Deterministic Finite


Automata (DFA)-

4. Convert the following Non-Deterministic Finite Automata (NFA) to Deterministic Finite


Automata (DFA)-

5. Construct a DFA, equivalent to the NFA given in figure

6. Write the tabular representation for the following automata


1. C
2. B
3. D
4. C
5. D
6. A
7. C
8. A
9. C
10. A
11. D
12. D
13. A
14.
15.
16.
17.
18.
19.
20.

You might also like