AMCAT Automata and Formal Languages

Question 1

Which of the following languages can be recognized by a Deterministic Finite Automaton (DFA)?

Accepted Answer

The set of all strings over {a, b} that end with 'ab'

Answer

The set of all strings over {a, b} with an equal number of a's and b's

Answer

The set of all palindromes over {a, b}

Answer

The set of all strings of the form a^n b^n where n >= 0

Question 2

What is the minimum number of states required in a DFA that accepts all binary strings divisible by 3?

Accepted Answer

3

Answer

2

Answer

4

Answer

5

Question 3

Which of the following is NOT a property of regular languages?

Accepted Answer

Ability to express a^n b^n for arbitrary n

Answer

Closure under union

Answer

Closure under intersection

Answer

Closure under complementation

Question 4

In the Chomsky hierarchy, which type of grammar generates context-free languages?

Accepted Answer

Type 2

Answer

Type 0

Answer

Type 1

Answer

Type 3

Question 5

A non-deterministic finite automaton (NFA) has 5 states. What is the maximum number of states in an equivalent DFA obtained by the subset construction method?

Accepted Answer

32

Answer

5

Answer

10

Answer

25

Question 6

Which of the following is true about the Pumping Lemma for regular languages?

Accepted Answer

It can be used to prove that a language is NOT regular

Answer

It can be used to prove that a language IS regular

Answer

It applies only to context-free languages

Answer

It states that all strings in a regular language can be pumped