Practice Test GeeksAMCAT Practice Test
← All AMCAT Flashcard Decks

AMCAT Automata and Formal Languages Flashcards

6 cards from real AMCAT practice questions. Tap to flip, then mark Knew It or Still Learning — missed cards come back until you master them.

Read the first 6 AMCAT Automata and Formal Languages flashcards as text

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

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

    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).

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

    Answer: 3

    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.

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

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

    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.

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

    Answer: Type 2

    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.

  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?

    Answer: 32

    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.

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

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

    The Pumping Lemma for regular languages provides a necessary condition for regularity. If a language fails to satisfy the Pumping Lemma, it is provably NOT regular. However, satisfying the lemma does not guarantee regularity, so it cannot prove a language IS regular.