Coursify

Finite Automata: Which Option Is NOT Accepted?

Finite Automata: Which Option Is NOT Accepted?

Verified Sources
Nov 4, 2026

Finite automata (DFA/NFA) accept exactly the regular languages—languages describable by a finite amount of memory (states). A key consequence is that some patterns (like matching across unbounded distance) are not regular, hence cannot be accepted by any finite automaton. In this question, the options (i)–(iv) mix regular and non-regular properties; the correct “NOT accepted” choice is the one whose language is non-regular.2

We analyze each option:

  • (ii) Strings with even number of a’s is regular: a DFA just tracks parity with 2 states.
  • (iii) Binary strings divisible by 3 is regular: a DFA can track the remainder modulo 3 using 3 states.
  • (iv) Strings ending with “ab” is regular: a DFA needs only to remember whether the last symbol(s) match “a”, then “ab”.
  • (i) Palindromes are not regular (over any alphabet with at least two symbols). Hence NOT accepted by finite automata.2

Summary answer

✅ NOT accepted by finite automata: (i) Palindromes.2

Footnotes

  1. Regular language and automata overview (Wikipedia) - https://en.wikipedia.org/wiki/Regular_language - Explains regular languages and their connection to finite automata. ↩ ↩2 ↩3

  2. Palindrome language is not regular (Wikipedia) - https://en.wikipedia.org/wiki/Palindrome - Discusses why palindromes are not regular languages. ↩ ↩2 ↩3

  3. Even number of occurrences (DFA via parity) (Wikipedia) - https://en.wikipedia.org/wiki/Deterministic_finite_automaton - Describes DFA state-based acceptance; parity example fits DFA reasoning. ↩

  4. Modulo languages / DFA for divisibility (Wikipedia) - https://en.wikipedia.org/wiki/Modular_arithmetic - Provides the modulo concept underlying divisibility tracking. ↩

  5. Regular languages / suffix patterns recognized by automata (Wikipedia) - https://en.wikipedia.org/wiki/Regular_language - Notes regular languages include patterns recognized by finite state machines (suffix-based properties). ↩

Fast Rule of Thumb

If the property requires comparing the first half with the second half for arbitrary length (unbounded symmetry), it’s likely not regular (so not DFA/FA). Palindromes are the classic example.2

Footnotes

  1. Regular language and automata overview (Wikipedia) - https://en.wikipedia.org/wiki/Regular_language - Explains regular languages and their connection to finite automata. ↩

  2. Palindrome language is not regular (Wikipedia) - https://en.wikipedia.org/wiki/Palindrome - Discusses why palindromes are not regular languages. ↩

Even if some DFA *looks* plausible...

Finite automata have finite memory. If you can’t store enough information about the input length to verify a condition, the language is probably not regular (and thus not FA-accepted). This is why palindromes fail.2

Footnotes

  1. Regular language and automata overview (Wikipedia) - https://en.wikipedia.org/wiki/Regular_language - Explains regular languages and their connection to finite automata. ↩

  2. Palindrome language is not regular (Wikipedia) - https://en.wikipedia.org/wiki/Palindrome - Discusses why palindromes are not regular languages. ↩

Decide which option is NOT accepted by finite automata

  1. 1
    Step 1

    Finite automata accept exactly regular languages—properties recognizable with finitely many states.

    Footnotes

    1. Regular language and automata overview (Wikipedia) - https://en.wikipedia.org/wiki/Regular_language - Explains regular languages and their connection to finite automata. ↩

  2. 2
    Step 2

    Check whether each option depends only on bounded memory (like parity or mod) or needs unbounded matching.

  3. 3
    Step 3

    Use two-state parity tracking (even/odd count). This is regular, so accepted.

    Footnotes

    1. Even number of occurrences (DFA via parity) (Wikipedia) - https://en.wikipedia.org/wiki/Deterministic_finite_automaton - Describes DFA state-based acceptance; parity example fits DFA reasoning. ↩

  4. 4
    Step 4

    Track the remainder mod 3 while reading bits left-to-right; this is a finite-state mod computation, so regular.

    Footnotes

    1. Modulo languages / DFA for divisibility (Wikipedia) - https://en.wikipedia.org/wiki/Modular_arithmetic - Provides the modulo concept underlying divisibility tracking. ↩

  5. 5
    Step 5

    Track the last few symbols needed to confirm the suffix; suffix checks are regular, so accepted.

    Footnotes

    1. Regular languages / suffix patterns recognized by automata (Wikipedia) - https://en.wikipedia.org/wiki/Regular_language - Notes regular languages include patterns recognized by finite state machines (suffix-based properties). ↩

  6. 6
    Step 6

    Palindromes require matching symbols from opposite ends for arbitrarily long strings; the language is not regular, so no finite automaton can accept it.2

    Footnotes

    1. Regular language and automata overview (Wikipedia) - https://en.wikipedia.org/wiki/Regular_language - Explains regular languages and their connection to finite automata. ↩

    2. Palindrome language is not regular (Wikipedia) - https://en.wikipedia.org/wiki/Palindrome - Discusses why palindromes are not regular languages. ↩

How this question is usually solved (conceptual roadmap)

Regular vs. non-regular

Step 1

Finite automata correspond to regular languages."

Footnotes

  1. Regular language and automata overview (Wikipedia) - https://en.wikipedia.org/wiki/Regular_language - Explains regular languages and their connection to finite automata. ↩

Look for unbounded matching

Step 2

Palindromes require global symmetry; that’s non-regular."

Footnotes

  1. Palindrome language is not regular (Wikipedia) - https://en.wikipedia.org/wiki/Palindrome - Discusses why palindromes are not regular languages. ↩

Confirm the others are regular

Step 3

Even-parity, mod divisibility, and fixed suffix are regular patterns.3"

Footnotes

  1. Even number of occurrences (DFA via parity) (Wikipedia) - https://en.wikipedia.org/wiki/Deterministic_finite_automaton - Describes DFA state-based acceptance; parity example fits DFA reasoning. ↩

  2. Modulo languages / DFA for divisibility (Wikipedia) - https://en.wikipedia.org/wiki/Modular_arithmetic - Provides the modulo concept underlying divisibility tracking. ↩

  3. Regular languages / suffix patterns recognized by automata (Wikipedia) - https://en.wikipedia.org/wiki/Regular_language - Notes regular languages include patterns recognized by finite state machines (suffix-based properties). ↩

Pick the non-FA option

Step 4

Therefore, (i) Palindromes is the correct answer."

Acceptance likelihood by FA (regular vs non-regular pattern)

Regular-pattern properties can be accepted by finite automata; non-regular cannot.

Key concept checkpoints

Finite Automata and Regular Languages (overview)

Knowledge Check

Question 1 of 4
Q1Single choice

Which of the following is NOT accepted by finite automata?

Explore Related Topics

1

FIRST Set for Terminals: Choosing the Correct Answer

2

Push-Down Automaton and Grammar Classes (MCQ Practice)

3

Language Theory: Interpreting the Regular Expression $(a \mid b)^*$

Browse all research articles