Automata and complexity theory

In formal language theory, what are the two criteria for a set of symbols to be considered an alphabet ($\Sigma$)?

It must be finite and non-empty.

What is the result of raising any alphabet to the power of zero ($\Sigma^0$)?

The set containing only the empty string ${\lambda}$ (or ${\epsilon}$).

The set of all possible non-empty strings formed from an alphabet is known as the _____.

Positive Closure (or Kleene Plus)

What is the mathematical definition of the Kleene Plus ($\Sigma^+$)?

$\Sigma^+ = \Sigma^1 \cup \Sigma^2 \cup \Sigma^3 \dots$

Term: Kleene Closure (Kleene Star)

Definition: The set of all possible strings of any discrete length, from zero to infinity, generated using symbols in $\Sigma$.

How is the Kleene Star ($\Sigma^*$) mathematically related to the Kleene Plus ($\Sigma^+$)?

$\Sigma^* = \Sigma^0 \cup \Sigma^+$

Which class of languages requires zero auxiliary memory and only tracks repeating patterns or static counts?

Regular Languages

Name the weakest machines capable of recognising Regular Languages.

Deterministic Finite Automata (DFA) or Nondeterministic Finite Automata (NFA).

What memory structure distinguishes a Pushdown Automaton (PDA) from a Finite Automaton?

A single infinite Last-In, First-Out (LIFO) Stack.

The language $L = {a^n b^n \mid n \ge 0}$ belongs to which language category?

Context-Free Languages (CFL).

Why is a stack sufficient to recognise the language of even-length palindromes $L = {ww^R \mid w \in {a, b}^*}$?

The second half of the string matches the reverse of the first half, fitting the LIFO structure.

Which automaton is used to recognise Context-Sensitive Languages (CSL)?

Linear Bounded Automaton (LBA).

What is the physical tape restriction of a Linear Bounded Automaton?

The tape length is strictly limited to the size of the input string.

The language $L = {a^n b^n c^n \mid n \ge 0}$ cannot be recognised by a PDA because it involves _____ dependent variables.

Three

What is the term for the most powerful abstract computational model that recognises Recursively Enumerable Languages?

Turing Machine.

Which language class contains the Halting Problem?

Recursively Enumerable Languages.

How does the computational power of a multi-tape Turing Machine compare to a standard single-tape Turing Machine?

They have identical computational power and recognise the same languages.

What is the primary utility of a Multi-tape Turing Machine over a single-tape model?

It drastically reduces execution time overhead for certain tasks.

Matching the copy language $L = {ww}$ takes $O(n^2)$ time on a single-tape TM, but how much time on a multi-tape TM?

$O(n)$

In a Multi-dimensional Turing Machine, in which directions can the read-write head move?

Up, Down, Left, or Right.

How is a Nondeterministic Turing Machine (NTM) simulated by a deterministic TM?

By using a breadth-first search tree of all possible execution paths.

Concept: Universal Turing Machine (UTM)

Definition: An abstract machine that takes an encoded TM description and an input string to simulate that TM's execution.

What defines an 'Off-line' Turing Machine?

It separates data from working memory using a read-only input tape and a separate read-write storage tape.

A language class is 'closed' under an operation if performing that operation on members of the class results in _____.

A language that remains within the same class.

Are Context-Free Languages closed under intersection?

No.

Are Context-Free Languages closed under complementation?

No.

What is the result of intersecting a Context-Free Language with a Regular Language?

The result is guaranteed to be a Context-Free Language.

Recursively Enumerable languages are NOT closed under which specific logical operation?

Complement.

If a language $L$ and its complement $\bar{L}$ are both recursively enumerable, what does $L$ become?

A Recursive (decidable) language.

While computability theory focuses on whether a problem is solvable, _____ theory focuses on the resources required.

Complexity

How many components (tuples) define a DFA or NFA?

Five (5-tuple).

In the DFA 5-tuple $M = (Q, \Sigma, \delta, q_0, F)$, what does $Q$ represent?

A finite, non-empty set of internal states.

What is the formal transition function definition for a DFA?

$\delta : Q \times \Sigma \to Q$

How does the transition function for an NFA ($\delta : Q \times (\Sigma \cup {\epsilon}) \to P(Q)$) differ from a DFA?

It maps to the power set of states, allowing for multiple, zero, or epsilon transitions.

How many components define a Pushdown Automaton (PDA)?

Seven (7-tuple).

In a PDA's 7-tuple, what is the meaning of the symbol $\Gamma$ (Gamma)?

The stack alphabet (symbols allowed to be pushed onto the stack).

What does $Z_0$ represent in the PDA 7-tuple definition?

The designated start stack symbol (bottom-of-stack anchor).

In the PDA transition function $\delta : Q \times (\Sigma \cup {\epsilon}) \times \Gamma \to P(Q \times \Gamma^)$, what does the $\Gamma^$ output represent?

The string of symbols that replaces the top character of the stack.

How many components define a Linear Bounded Automaton (LBA)?

Eight (8-tuple).

In an LBA definition, what is the purpose of the symbols $\kappa$ (Cent) and $\$$?

They act as boundary markers for the left and right ends of the input tape.

What is the formal definition of the tape alphabet $\Gamma$ in an LBA or TM relative to the input alphabet $\Sigma$?

$\Sigma \subset \Gamma$ (the tape alphabet includes input symbols and additional workspace symbols).

The standard single-tape Turing Machine is formally defined as a _____-tuple.

Seven (7-tuple).

In the Turing Machine 7-tuple, what does the symbol $B$ represent?

The blank symbol that fills the infinite expanse of the tape.

The Turing Machine transition function $\delta : Q \times \Gamma \to Q \times \Gamma \times {L, R}$ dictates three actions: update state, write symbol, and _____.

Shift the tape head one step Left or Right.

Which language category is closed under Union, Concatenation, and Kleene Star, but NOT Intersection or Complement?

Context-Free Languages (CFL).

Under which operation are Regular, CFL, CSL, and RE languages all consistently closed?

Union (or Concatenation, or Kleene Star).

Which language class is only recognised by a machine with a LIFO memory structure?

Context-Free Languages (CFL).

True or False: Nondeterminism increases the language-recognition power of a Pushdown Automaton.

True (implied by the transition function mapping to a power set).

True or False: Nondeterminism increases the language-recognition power of a Turing Machine.

False.

Concept: Finite Automata

Definition: The simplest machines with zero auxiliary memory, tracking patterns via a fixed number of states.

What is the 'Profile' of a DFA's transition complexity?

It reads a symbol and changes state.

What is the 'Profile' of a PDA's transition complexity?

It reads a symbol, pops from the stack, changes state, and pushes to the stack.

What is the 'Profile' of a TM's transition complexity?

It reads a cell, overwrites the cell, and moves the head Left or Right.

Which machine uses 'Linear Bounded' space for its tape?

Linear Bounded Automaton (LBA).

In the LBA tuple, what is the relation between the input alphabet and the tape alphabet?

$\Sigma \subset \Gamma$.

Which specific machine is the theoretical blueprint for modern programmable computers?

Universal Turing Machine (UTM).

Context-Sensitive Languages handle three or more dependent variables or _____ matching structures.

Out-of-order

Why does the intersection of $L_1 = {a^n b^n c^m}$ and $L_2 = {a^m b^n c^n}$ prove CFL intersection failure?

The intersection is $a^n b^n c^n$, which requires tracking three dependent variables and is not context-free.

Is the blank symbol $B$ allowed to be part of the input alphabet $\Sigma$ in a Turing Machine?

No ($B \in \Gamma$ but $B \notin \Sigma$).

Which machine handles 'nested tracking' or 'matching pairs'?

Pushdown Automaton (PDA).

What is the highest level of the language hierarchy mentioned, described by unrestricted grammars?

Recursively Enumerable Languages.

What is the transition function output for an LBA?

$Q \times \Gamma \times {L, R}$.

Which language class is recognised by a Turing Machine with a restricted tape length?

Context-Sensitive Languages (CSL).

What is the purpose of the 'State Register' in a basic Turing Machine?

To track the current internal control state of the machine.

In a Multi-head TM, when does the machine make a state transition?

After reading the symbols under all $k$ heads simultaneously.

What does the symbol $F$ represent in all the defined automata tuples?

The set of final or accepting states ($F \subseteq Q$).

What does $q_0$ represent in all the defined automata tuples?

The designated start state ($q_0 \in Q$).

Are Recursively Enumerable languages closed under Intersection?

Yes.

Are Context-Sensitive Languages closed under Complement?

Yes.

Which language class is described as 'any language that can be described by a step-by-step algorithm'?

Recursively Enumerable Languages.

What determines the length of the strings generated from an alphabet in formal language theory?

Raising the alphabet to a mathematical power.

In the context of PDAs, what does 'LIFO' stand for?

Last-In, First-Out.

Which machine type allows for branching into parallel execution paths?

Nondeterministic Turing Machine (NTM).

Which closure property is true for all four language classes (Regular, CFL, CSL, RE)?

Union (or Concatenation, or Kleene Star).

The transition function $\delta$ is often called the _____ of the machine.

Brain

In a TM, what symbol fills the tape before and after the input string?

The blank symbol ($B$).