Which of the following is a primary branch of Automata Theory? A) Graph Theory B) Computational Complexity Theory C) Software Engineering D) Networking

B) Computational Complexity Theory

True or False: A Turing machine is the most commonly examined model of computation.

True

Fill in the blank: The smallest building block of a language is called a ______.

Symbol

What is the language generated by the grammar S → aSb | ε?

L(G) = {a^n b^n | n ≥ 0}

Riddle: I can describe languages and generate strings, with rules and symbols that define my wings. What am I?

A grammar

Which type of language is recognized by a Pushdown Automaton (PDA)? A) Regular B) Context-Free C) Context-Sensitive D) Unrestricted

B) Context-Free

Fill in the blank: A grammar is defined by a finite set of production rules, which are used to generate ______.

Strings of a language

True or False: Every Non-deterministic Finite Automaton (NFA) can be converted into a Deterministic Finite Automaton (DFA).

True

What is the formal definition of a Context-Free Grammar (CFG)?

A CFG is defined by productions of the form A → β, where A is a non-terminal and β is a string of terminals and non-terminals.

Which of the following is a characteristic of computable functions? A) They can be calculated using a finite amount of resources B) They always terminate with an output C) They can be defined for infinite inputs D) A and B

D) A and B