⭐ 3 MARK IMPORTANT THEORY ANSWERS (NEW)
1) Deterministic vs Non-Deterministic Computation (3 Marks)
Deterministic computation means that for every state and input symbol, the
machine has exactly one possible next move. Therefore, the entire
computation path is uniquely defined.
Non-deterministic computation allows multiple possible next moves for the
same state and input symbol. The machine “branches” into many parallel
paths, and a string is accepted if at least one path leads to an accepting
state.
Examples:
DFA and DTM are deterministic.
NFA, NPDA, and NTM are non-deterministic.
2) Closure Properties of Regular Languages (3 Marks)
Regular languages are closed under several operations.
If L₁ and L₂ are regular, then the following languages are also regular:
Union: L₁ ∪ L₂ is regular.
Intersection: L₁ ∩ L₂ is regular.
Complement: If L is regular, then its complement L′ is also regular.
Concatenation: L₁L₂ is regular.
Kleene Star: L* is regular.
These properties help in proving languages regular or non-regular.
3) Types of Language Acceptance (3 Marks)
A language may be accepted by an automaton in different ways:
Acceptance by Final State:
The automaton accepts a string if it ends in one of the final states after
reading the full input.
Acceptance by Empty Stack (PDA):
A PDA accepts a string by emptying its entire stack, regardless of the final
state.
Acceptance by Halting ™:
A Turing Machine accepts a string if it halts in an accepting state.
All three methods define how machines verify valid strings.
4) Leftmost and Rightmost Derivation (3 Marks)
A derivation shows how a string is generated from the start symbol using
production rules.
Leftmost Derivation (LMD): Always replace the leftmost non-terminal first.
Rightmost Derivation (RMD): Always replace the rightmost non-terminal first.
Both forms generate the same string but follow different replacement orders.
They are used in parsing and grammar analysis.
5) Limitations of Finite Automata (3 Marks)
Finite Automata cannot recognize languages that need memory, such as:
Balanced strings like aⁿbⁿ.
Nested structures or matching brackets.
Context-free patterns requiring stack usage.
FA has limited power because it has fixed number of states and no auxiliary
storage. PDA and TM overcome these limitations.
⭐ 2 MARK IMPORTANT THEORY ANSWERS (NEW)
1) What is an Alphabet? (2 Marks)
An alphabet is a finite, non-empty set of symbols used to form strings.
Example: Σ = {0,1} or Σ = {a,b,c}.
2) Define Instantaneous Description (ID). (2 Marks)
An ID represents the complete status of an automaton at a given moment.
For FA: (state, remaining input).
For PDA: (state, input, stack).
For TM: (state, tape contents, head position).
3) What is a Configuration in Turing Machine? (2 Marks)
A configuration is a detailed description of the TM including:
Current state
Tape contents
Position of read/write head
It shows the machine’s exact situation at a specific step.
4) Define Homomorphism. (2 Marks)
A homomorphism is a mapping from symbols of one alphabet to strings over
another alphabet.
If h(a) = 01, h(b) = 10, then h(ab) = 0110.
It preserves concatenation.
5) Define Prefix-Free Language. (2 Marks)
A language is prefix-free if no string in the language is a prefix of another
string in the same language.
Example: {10, 110, 1110} is prefix-free.
6) What is Recursive Language? (2 Marks)
A recursive language is a language for which a Turing Machine always halts
and correctly accepts or rejects every string. It never loops forever.
7) Define Nullable Symbol. (2 Marks)
A nullable symbol is a non-terminal in a grammar that can derive the empty
string (ε). It may require multiple productions to reach ε.
8) What is Complement of a Language? (2 Marks)
If L is a language over Σ, then the complement L′ contains all strings over Σ
not present in L.
L′ = Σ* – L.
9) What is Concatenation of Languages? (2 Marks)
For languages L₁ and L₂,
L₁L₂ = { xy | x ∈ L₁ and y ∈ L₂ }.
Strings from L₁ are joined with strings from L₂.
10) Define Derivation. (2 Marks)
A derivation is the step-by-step application of grammar rules starting from
the start symbol to generate a string.
If you want, I can convert all these into a clean PDF for you before your exam
❤️