Automata Theory

MCQs - Introduction Part 1

NEXT
Distribute Education
Menu
Unit 1

Overview: Automata, Computability and Complexity, Alphabet, Symbol, String, Formal Languages.

Q1 – Let S be an infinite set and S1 U S2 U S3 U …. U SN be sets such that, then
  1. at least one of the sets Si is a finite set
  2. not more than one of the sets Si can be finite
  3. at least one of the sets Si is an infinite
  4. not more than one of the sets Si can be infinite

Ans – (3)

Explanation – If all the sets were finite, then their union would also be finite.

Because Finite ∪ Finite = Finite. (Finite union of finitely many finite sets is still finite). But this is impossible because S is given infinite. Therefore, at least one Si must be infinite.

Q2 – Who is most credited as the foundational father of the Theory of Computation for introducing a mathematical model that defines the limits of algorithmic computation?
  1. Alonzo Church
  2. Kurt Gödel
  3. Alan Turing
  4. John von Neumann

Ans – (3)

Explanation – While Church, Gödel, and others made vital contributions, Alan Turing is most prominently regarded as the father of the field. His 1936 paper introduced the Turing Machine, a conceptual model that formalized computation, defined decidability, and established the fundamental limits of what can be computed algorithmically. The Church-Turing thesis later united his work with Alonzo Church’s lambda calculus, but Turing’s model became the central reference for computation theory.

Q3 – Which of the following are the two fundamental components that define a formal language, as described in the text?
  1. Compilers and Interpreters
  2. Variables and Functions
  3. Symbols and Rules of Formation
  4. Syntax and Semantics

Ans – (3)

Explanation – A formal language consists of a set of symbols and some rules of formation by which these symbols can be combined into entities called sentences. Symbols and rules of formation are the stated components.

Q4 – What constitutes a formal language as a complete set?
  1. The set of all possible symbols.
  2. The set of all valid formation rules.
  3. The set of all sentences permitted by the rules of formation.
  4. The set of all abstractions of programming languages.

Ans – (3)

Explanation – “A formal language is the set of all sentences permitted by the rules of formation.” This makes it a complete, well-defined collection of valid strings.

Q5 – Which concept is NOT a required component for defining a formal language?
  1. A set of symbols
  2. Rules for combining symbols
  3. The meaning or interpretation of the sentences
  4. The collection of all valid sentences

Ans – (3)

Explanation – It only explains the structure of a formal language – symbols, syntax rules, and the set of valid sentences. It does not explain meaning (semantics), which is a separate topic.

Q6 – If a new combination of symbols does not follow the established “rules of formation,” what is its status relative to the formal language?
  1. It is a sentence with an error.
  2. It is not a sentence within that formal language.
  3. It is a member of a different formal language.
  4. It changes the rules of formation.

Ans – (2)

Explanation – The language is defined strictly as the set of permitted sentences. If a string of symbols violates the formation rules, it is not permitted and therefore is not part of that language’s set of sentences.

Q7 – The description of a formal language in the text is most focused on its:
  1. Pragmatics (how it is used)
  2. Semantics (what it means)
  3. Syntax (its structure)
  4. Implementation (how it is executed)

Ans – (2)

Explanation – The entire description revolves around form and structure: symbols, rules for combining them (syntax), and the resulting well-formed sentences. Meaning, use, and execution are not addressed.

Q8 – The rules of formation specify how to combine ______ into ______.
  1. symbols, sentences
  2. programming languages, abstractions
  3. sentences, meanings
  4. entities, sets

Ans – (1)

Explanation – Because rules of formation (syntax rules) tell us how to combine symbols to form valid sentences (strings) in a formal language.

Q9 – Which of the following is the most accurate analogy for the definition of a formal language?
  1. A formal language is like a dictionary of words.
  2. A formal language is like a grammar rulebook that defines all possible correct sentences in a language.
  3. A formal language is like a specific novel written in English.
  4. A formal language is like a translator between two languages.

Ans – (2)

Explanation – A formal language contains rules of formation (grammar rules). These rules can generate an infinite set of valid sentences. The other options describe only words (a), a single example (c), or translation (d).

Q10 – If L = {a, ab} and M = {ε, b}, then L∘M = ?
  1. {a, ab, ab, abb}
  2. {a, ab, abb}
  3. {a, ab, b, abb}
  4. {a, ab, b, abb, ε}

Ans – (2)

Explanation – Concatenation: a∘ε = a, a∘b = ab, ab∘ε = ab, ab∘b = abb → {a, ab, abb} (remove duplicates).

Q11 – Which statement about {ε} is true?
  1. It’s the empty language
  2. It contains infinite strings
  3. |{ε}| = 1
  4. It’s not a language over any Σ

Ans – (3)

Explanation – {ε} has exactly one string (ε).

Q12 – If Σ₁ = {0} and Σ₂ = {0, 1}, then:
  1. Σ₁* is finite
  2. Σ₂* is uncountable
  3. Σ₁* ⊂ Σ₂*
  4. Every string in Σ₁* is in Σ₂*

Ans – (4)

Explanation – Σ₁* = {ε, 0, 00, …} ⊆ Σ₂* (since both contain ε, 0, 00…).

Q13 – Over Σ = {a, b}, how many strings have length ≤ 2?
  1. 4
  2. 7
  3. 8
  4. 6

Ans – (2)

Explanation – Count: ε (1), length 1: 2, length 2: 4 → total 7.

Q14 – Consider Σ = {a}. Let w = ε (empty string). Which is true?
  1. ww = w
  2. |www| = 0
  3. w is a prefix of every string in Σ*
  4. All of the above

Ans – (4)

Explanation – ww = ε, |www| = 0, and ε is prefix of every string.

Q15 – In formal language theory, a “language” is defined as:
  1. A set of strings over a finite alphabet
  2. A set of symbols
  3. A set of grammars
  4. A set of automata

Ans – (1)

Explanation – Many beginners confuse language with alphabet or grammar.

Q16 – Which of these sets is countably infinite?
  1. The set of all Turing machines
  2. The set of all computable functions from ℕ to {0,1}
  3. The set of all recursively enumerable languages
  4. All of the above

Ans – (4)

Explanation – All three are countable. TMs can be encoded as strings, also computable functions correspond to TMs, languages correspond to TMs that accept them.

Q17 – The set of all decidable languages over Σ = {0, 1} is:
  1. Finite
  2. Countably infinite
  3. Uncountably infinite
  4. Neither countable nor uncountable

Ans – (2)

Explanation – Each decidable language corresponds to a Turing machine that halts on all inputs. Turing machines can be enumerated (countable), but there are uncountably many languages total. So decidable languages form a countable subset of all languages.

Q18 – Let Σ = {0, 1}. Consider the following statements:
I. The number of strings of length exactly over Σ is .
II. The set of all strings over Σ is countably infinite.
III. For any alphabet Σ with |Σ| ≥ 2, the set of all strings over Σ is uncountable.
Which of the above is/are false?
  1. Only III
  2. Only I
  3. II and III
  4. None

Ans – (1)

Explanation – I and II are true. III is false — the set of all finite strings over any finite alphabet is countable, but the set of all infinite sequences is uncountable.

Q19 – The set of all finite subsets of is:
  1. Finite
  2. Countably infinite
  3. Uncountably infinite
  4. None

Ans – (2)

Explanation – because each finite subset can be encoded as a binary string or integer.

Q20 – Let S be an infinite set and S1 U S2 U S3 U …. U SN be sets such that, then
  1. at least one of the sets Si is a finite set
  2. not more than one of the sets Si can be finite
  3. at least one of the sets Si is an infinite
  4. not more than one of the sets Si can be infinite

Ans – (3)

Explanation – If all the sets were finite, then their union would also be finite.

Because Finite ∪ Finite = Finite. (Finite union of finitely many finite sets is still finite). But this is impossible because S is given infinite. Therefore, at least one  must be infinite.

NEXT

BOOKS

Peter linz Theory of Computation

TOC by KLP Mishra

Automata Theory by John E. Hopcraft

GATE Study Material
Previous Year Paper
Assignements