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

A DFA can recognize regular languages. 'Strings ending with ab' is a regular language because a DFA only needs to track the last two characters seen. The other options require memory of unbounded counts or positions, making them non-regular (context-free or beyond).

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

A number can have remainder 0, 1, or 2 when divided by 3. A DFA with 3 states (one for each possible remainder) can track the remainder as it reads each binary digit. The state representing remainder 0 is the accepting state.

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

Regular languages are closed under union, intersection, and complementation (options A, B, C). However, the language {a^n b^n | n >= 0} is a classic context-free language that is NOT regular, as proven by the Pumping Lemma for regular languages.

Question 4

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

Accepted Answer

Type 2

Answer

The Chomsky hierarchy classifies grammars into four types: Type 0 (unrestricted/recursively enumerable), Type 1 (context-sensitive), Type 2 (context-free), and Type 3 (regular). Context-free grammars (Type 2) have rules of the form A → α where A is a single non-terminal.

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

The subset construction converts an NFA to a DFA where each DFA state represents a subset of NFA states. With 5 NFA states, the power set has 2^5 = 32 possible subsets, so the equivalent DFA can have at most 32 states.

AMCAT Practice Test

AMCAT Practice Test

AMCAT Automata and Formal Languages