NEW
Font size
WorksheetsContext-Free Grammar
Total questions: 77
Worksheet time: 39mins
A rule in a CFG can be applied anywhere the single non-terminal (variable) on the left side appears, regardless of its context (surrounding symbols). Which of the following best describes a context-free grammar?
A grammar where rules depend on surrounding symbols
A grammar where rules can be applied regardless of context
A grammar with no variables
A grammar with only terminal symbols
In a context-free grammar, the rule format is ______ → β (Only a single variable on the left side). Fill in the blank.
A
S
α
B
Simple Example: Language L = {aⁿbⁿ | n ≥ 1}. This language requires an equal number of a's and b's. Which of the following strings belong to this language?
ab
aabb
aaabbb
All of the above
What does the language L = anbn∣n≥1 require?
An equal number of a's and b's
More a's than b's
More b's than a's
Only a's
Fill in the blank: The CFG rules for the language L = {a^n b^n | n ≥ 1} are: S → aSb S → ε
ab
a
b
ε
Fill in the blank: In the parsing example for deriving aabb, the sequence of derivations is: S → aSb → a(ab)b → ____ Write the final derived string.
aabb
abab
abbb
aaab
What is Chomsky Normal Form (CNF)?
A way to represent Regular Grammars
A highly restricted and standardized way to represent Context-Free Grammars (CFGs)
A method for parsing natural languages
A type of programming language
Chomsky Normal Form (CNF) enforces that every single production rule in the grammar must strictly follow one of the two simple structures below.
True
False
What is Binary Production in formal grammar?
A non-terminal must derive exactly one terminal symbol
A non-terminal must derive exactly two non-terminals
A non-terminal must derive three non-terminals
A non-terminal must derive a real word/character
What is Terminal Production in formal grammar?
A non-terminal must derive exactly two non-terminals
A non-terminal must derive exactly one terminal symbol
A non-terminal must derive three non-terminals
A non-terminal must derive a phrase
Fill in the blank: In Binary Production, a non-terminal (A) must derive exactly ___ non-terminals.
two
one
three
four
Fill in the blank: In Terminal Production, a non-terminal (A) must derive exactly ___ terminal symbol.
one
two
three
zero
What is the primary role of CNF?
To make grammar rules more complex
To enable efficient and algorithmic parsing (understanding sentence structure) by a computer
To slow down parsing algorithms
To remove binary branching
In complex CFG, rules are ______ and complex. (e.g., A → aBCD or A → B)
arbitrary
simple
fixed
predictable
In CNF, rules are ______ and uniform. (e.g., A → BC or A → a)
simple
complex
ambiguous
variable
What does CNF force the Parse Tree to be?
Single branching
Binary branching
Ternary branching
No branching
Which algorithm requires CNF to work?
Dijkstra's Algorithm
CYK Algorithm (Cocke-Younger-Kasami)
Merge Sort
Quick Sort
Which of the following is NOT a valid rule in Chomsky normal form?
A) A → BC
B) A → a
C) A → B
D) S → ε (where S is the start variable)
In Chomsky normal form, the rule S → ___ is permitted, where S is the start variable.
ε
a
S
AB
In Chomsky normal form, 'a' must be a terminal and 'A', 'B', 'C' must be variables.
True
False
A context-free grammar is in Chomsky normal form if every rule is of one of the following forms: A → BC, A → a. Which of the following forms is allowed in Chomsky normal form?
A → BC
A → a
S → ε (where S is the start variable)
All of the above
What is the first step to convert any CFG to Chomsky normal form?
Add a new start symbol
Remove null productions
Eliminate unit productions
Convert terminals in rules to variables
Which type of rules should be eliminated in the second step of converting any CFG to Chomsky normal form?
ε rules of the form A → ε
Unit rules of the form A → B
Left-recursive rules of the form A → Aa
Terminal rules of the form A → aB
What is the third step in converting any CFG to Chomsky normal form?
Eliminate unit rules of the form A → B
Remove null productions
Remove useless symbols
Convert terminals in rules to non-terminals
In the final step of converting any CFG to Chomsky normal form, what should the remaining rules be converted into?
Proper form (2 non-terminal or 1 terminal)
Unit productions (single non-terminal)
Epsilon productions (empty string)
Left-recursive form
Step 1 in converting a CFG to Chomsky normal form is to add a new start symbol. What is the new rule that should be created?
A) S₀ → S
B) S → S₀
C) S₀ → A
D) S → A
In converting a CFG to Chomsky normal form, the new start symbol added is ____ and it is not used in the original CFG.
S₀
S
A
X
Convert a CFG to Chomsky normal form: What is the first step in eliminating all ε rules from a context-free grammar (CFG), where A is not the start variable?
Eliminate all ε rules A → ε
Add new rules with A deleted
Replace R → A with R → ε
Remove all terminal symbols
Convert a CFG to Chomsky normal form: For each rule with an occurrence of A on the right-hand side, what should you do?
Add a new rule with the A deleted
Replace A with ε
Remove the rule entirely
Add a terminal symbol
Convert a CFG to Chomsky normal form: Fill in the blank. If we have R → A, replace it with ______ unless we had already removed R → ε.
R → ε
R → A | ε
R → A | R
R → εA
Convert a CFG to Chomsky normal form: Given the rule R → uAvAw, what are the possible new rules after eliminating A → ε?
R → uAvAw | uvAw | uAvw | uvw
R → uAvAw | uAw | vAw | vw
R → uAvAw | uAvw | uvAw
R → uAvAw only
Step 3 in converting a CFG to Chomsky normal form is to eliminate all unit rules of the form A → B. What does this step require you to do?
Replace each variable with a terminal
Replace each alone variable with its value
Remove all terminals
Add new variables
In the process of eliminating unit rules when converting a CFG to Chomsky normal form, for each rule B → u, what new rule should be added?
A) A → B
B) A → u
C) B → A
D) u → A
Fill in the blank: Repeat the process of eliminating unit rules until ________ have been replaced.
all unit rules
some unit rules
no unit rules
the start symbol
Convert a CFG to Chomsky normal form: What is the proper form for the remaining rules in Chomsky normal form?
2 variables or one terminal
3 variables or one terminal
Only terminals
Only variables
Convert a CFG to Chomsky normal form: Fill in the blank: Replace each rule A → u₁u₂...uₖ, where k ≥ 3 and uᵢ is a variable or a terminal, with ____ rules.
k-1
k+1
2k
k
Convert a CFG to Chomsky normal form: Which of the following is the correct sequence for replacing a rule A → u₁u₂...uₖ in Chomsky normal form?
A) A → u₁A₁, A₁ → u₂A₂, ..., Aₖ₋₂ → uₖ₋₁uₖ
B) A → u₁u₂, A₁ → u₃u₄
C) A → u₁u₂u₃, A₁ → u₄u₅
D) A → u₁, A₁ → u₂
What is Chomsky Normal Form (CNF) in context-free grammar (CFG)?
A context free grammar (CFG) is in Chomsky Normal Form (CNF) if all production rules satisfy the following conditions: 1) A non-terminal generating a terminal (e.g.; X→x), 2) A non-terminal generating two non-terminals (e.g.; X→YZ), 3) Start symbol generating ε (e.g.; S→ε).
A context free grammar (CFG) is in Chomsky Normal Form (CNF) if all production rules generate only terminals.
A context free grammar (CFG) is in Chomsky Normal Form (CNF) if all production rules generate only non-terminals.
A context free grammar (CFG) is in Chomsky Normal Form (CNF) if all production rules generate only the start symbol.
Which of the following is NOT a condition for Chomsky Normal Form (CNF)?
A) A non-terminal generating a terminal (e.g.; X→x)
B) A non-terminal generating two non-terminals (e.g.; X→YZ)
C) A non-terminal generating three non-terminals (e.g.; X→XYZ)
D) Start symbol generating ε (e.g.; S→ε)
Consider the following grammars: G1 = {S→a, S→AZ, A→a, Z→z} G2 = {S→a, S→aZ, Z→a} Which grammar is in Chomsky Normal Form (CNF)?
G1
G2
Why is the grammar G2 not in Chomsky Normal Form (CNF)?
G2 is not in CNF as the production rule S→aZ contains terminal followed by non-terminal which does not satisfy the rules specified for CNF.
G2 is not in CNF because all production rules contain only terminals.
G2 is not in CNF as it has no start symbol.
G2 is not in CNF because it contains only non-terminals in every production.
If start symbol S is at the RHS of any production in the grammar, what new production should be created?
S0 → S
S → S0
S0 → ε
S → ε
What should you do if a rule contains ε (null production)?
Remove it by modifying other rules accordingly.
Leave it as it is without any changes.
Replace ε with a terminal symbol.
Ignore the rule completely.
If a rule has a single non-terminal on the RHS (e.g., A → B), what should you do?
Remove the rule
Replace it with B’s productions
Add a new start symbol
Remove all non-terminals
What should be done with non-reachable or non-generating symbols from the grammar?
Remove them from the grammar.
Mark them as start symbols.
Replace them with terminal symbols.
Add them to the production rules.
Step 3: Replace Terminals in Mixed Productions Eliminate terminals from RHS if they exist with other terminals or non-terminals. For example, the production rule X→xY can be decomposed as: Which of the above is the correct decomposition?
A) X→ZY, Z→x
B) X→YZ, Z→x
C) X→xY, Y→Z
Step 4: Reduce Productions with More Than Two Non-Terminals Eliminate RHS with more than two non-terminals. For example, the production rule X→XYZ can be decomposed as: Fill in the blanks: X→___, P→___
X→PZ, P→XY
X→XY, P→XZ
X→YZ, P→XY
X→PX, P→YZ
What is the limitation of FA (Finite Automata) related to the fact that they can only 'remember' a bounded amount of information?
They can process infinite memory
They can only remember a limited amount of information
They can solve all computational problems
They have unbounded memory
What is the simplest alteration that adds unbounded 'memory' to our machine?
Adding a stack (as in a pushdown automaton) is the simplest alteration that adds unbounded memory.
Increasing the number of states in the machine.
Adding a finite tape to the machine.
Allowing the machine to read input multiple times.
A more powerful machine should be able to recognize which of the following languages?
{0ⁿ1ⁿ : n ≥ 0}
{0ⁿ1ᵐ : n, m ≥ 0}
{0ⁿ1ⁿ2ⁿ : n ≥ 0}
{0*1*}
What does the tape alphabet represent in an NPDA diagram?
A) The set of symbols that can be read from the tape
B) The set of states in the automaton
C) The set of stack operations
D) The set of accept states
In the NPDA diagram, what is the symbol for the stack alphabet?
Σ
Γ (gamma)
δ
ε
Fill in the blank: The start state in an NPDA is the state where the computation _______.
begins
ends
halts
loops
Which of the following correctly describes the transition label format in the NPDA diagram?
(input symbol, stack symbol popped → stack symbol pushed)
(state, input symbol → stack symbol)
(stack symbol, input symbol → state)
(input symbol, state → stack symbol)
In the NPDA diagram, what does the transition '0, ε → 0' mean?
On reading '0' from the tape and popping ε from the stack, push '0' onto the stack.
On reading '0' from the tape and popping '0' from the stack, push ε onto the stack.
On reading ε from the tape and popping '0' from the stack, push '0' onto the stack.
On reading '0' from the tape and popping '0' from the stack, push '0' onto the stack.
What does NPDA stand for in the context of Pushdown Automata?
Nondeterministic Pushdown Automata
Normal Pushdown Automata
Non-Polynomial Deterministic Automata
Numerical Pushdown Automata
Which of the following is NOT a way to describe NPDA?
Diagram
Formal definition
Truth table
None of the above
What does 'nondeterministic' mean in the context of pushdown automata?
Only one possible next step
Potentially several choices of 'next step'
No choices of next step
Always deterministic
In NPDA operation, what does the 'read' component represent in the transition (read, pop, push)?
read a from tape, or don’t read from tape if a = ε
pop a symbol from the stack
push a symbol onto the stack
move the tape head to the right
In NPDA operation, what does the 'pop' component represent in the transition (read, pop, push)?
pop b from stack, or don’t pop from stack if b = ε
push b onto stack, or don’t push if b = ε
read b from input, or skip if b = ε
move to next state if b = ε
In NPDA operation, what does the 'push' component (c) represent in the transition (read, pop, push)?
push c onto stack, or don’t push onto stack if c = ε
pop c from stack, or don’t pop if c = ε
read c from input, or skip if c = ε
replace c with ε on stack
Which of the following is true about the values of a, b, and c in NPDA operation?
A) a ∈ (Σ ∪ {ε}), b, c ∈ (Γ ∪ {ε})
B) a ∈ (Γ ∪ {ε}), b, c ∈ (Σ ∪ {ε})
C) a, b, c ∈ (Σ ∪ {ε})
D) a, b, c ∈ (Γ ∪ {ε})
According to the formal definition, what does NPDA M = (Q, Σ, Γ, δ, q0, F) accept?
A string w ∈ Σ*
A string w ∈ Γ*
A string w ∈ Q*
A string w ∈ F*
Which of the following is true for a string w to be accepted by an NPDA?
w can be written as w1w2...wm ∈ (Σ ∪ {ε})*
w can be written as w1w2...wm ∈ (Γ ∪ {ε})*
w can be written as w1w2...wm ∈ (Q ∪ {ε})*
w can be written as w1w2...wm ∈ (F ∪ {ε})*
Fill in the blank: There exist states _____, r1, ..., rm for a string to be accepted by an NPDA.
r0
q0
p0
s0
Which of the following is NOT a requirement for a string to be accepted by an NPDA?
A) r0 = q0 and s0 = ε
B) (ri+1, b) ∈ δ(ri, wi+1, a), where si = at, si+1 = bt for some t ∈ Γ*
C) rm ∈ F
D) s0 = q0 and r0 = ε
For a string to be accepted by an NPDA, there must exist strings s0, s1, ..., sm in (Γ ∪ {ε})*.
True
False
Q in the 6-tuple (Q, Σ, Γ, δ, q₀, F) of NPDA is a finite set called the _______.
states
transitions
symbols
inputs
Σ in the 6-tuple (Q, Σ, Γ, δ, q₀, F) of NPDA is a finite set called the _______.
tape alphabet
state set
transition function
stack symbols
Γ in the 6-tuple (Q, Σ, Γ, δ, q₀, F) of NPDA is a finite set called the _______.
stack alphabet
input alphabet
state set
final states
δ: Q × (Σ ∪ {ε}) × (Γ ∪ {ε}) → ℘(Q × (Γ ∪ {ε})) is a function called the _______.
transition function
output function
acceptance function
state function
q₀ in the 6-tuple (Q, Σ, Γ, δ, q₀, F) of NPDA is an element of Q called the _______.
start state
final state
input symbol
transition function
F in the 6-tuple (Q, Σ, Γ, δ, q₀, F) of NPDA is a subset of Q called the _______.
accept states
start states
transition states
stack symbols
Given the NPDA with Σ = {0, 1} and Γ = {0, 1, $}, and the state transitions shown in the diagram, which of the following languages does this NPDA accept?
The set of all palindromes over {0, 1}
The set of all strings with equal number of 0's and 1's
The set of all strings of the form wwR , where w ∈ {0,1}*
The set of all strings ending with 1
What is one of the new capabilities of a Pushdown Automata?
Can multiply numbers
Can push symbol onto stack
Can sort data
Can add numbers
What is the function of the 'pop' operation in a Pushdown Automata?
Add a symbol to the stack
Remove a symbol from the stack
Sort the stack
Reverse the stack
Fill in the blank: The three main components of a Pushdown Automata are finite control, input tape, and _________.
stack
queue
register
counter
