COS3701 EXAM PACK
2024
QUESTIONS AND
ANSWERS
FOR ASSISTANCE CONTACT
EMAIL:
, lOMoARcPSD|44660598
COS3701 VIDEO BASED STUDY
NOTES
Question 1:Context Free Grammars
Question 1A & 1B: Creation of a regular expression and sketching a Determinist
Finite Automaton (DFA)
Question A necessitates the creation of a regular expression, while Question B
entails sketching a Deterministic Finite Automaton (DFA). Ensure that you thoroughly
watch the videos below to grasp the underlying concepts.
Watch Videos 1-18 For a general introduction to concepts
Examples for designing regular expressions
Examples for sketching a Deterministic Finite Automaton (DFA)
After watching the videos attempt all question A and B in the provided question
papers.
Question 1C: Developing a CFG (Context free Grammar)
The two videos below are an introduction to CFGs. They explain what CFGs are and
give a brief introduction on how CFGs are constructed.
Context Free Grammar & Context Free Languages
Definition of CFG with an Example || Context Free Grammar || TOC || Theory of
Computation|| FLAT| CD
After watching the introduction videos u will now watch the videos below which have
a number of examples being explained. The more examples you watch the better you
will understand the concepts.
Examples 1
Examples 2
20 More Examples
Question 1D: Convert a CFG to Chomsky Normal Form (CNF)
For this section start by watching the videos below to understand the concepts and
then attempt the questions on your own.
Video: Simplification of CFG (Reduction of CFG)
Video: Simplification of CFG (Removal of Unit Productions)
Video: Simplification of CFG (Removal of Null Productions)
1
, lOMoARcPSD|44660598
Video: Chomsky Normal Form & CFG to CNF Conversion
Video: Example, Conversion of CFG to Chomsky Normal Form
Chomsky Normal Form (CNF) is a specific way of writing context-free grammars
(CFGs) with certain restrictions on the production rules. These restrictions make the
grammar simpler and easier to analyze, while still being able to generate the same
language as the original CFG.
Here are the key rules for a CNF CFG:
1. Two types of production rules:
● Binary branching: Each rule can either have two non-terminals on the
right-hand side (B -> CD) or a single terminal (B -> a). This restriction
simplifies how rules can be applied and combined.
● Empty string (optional): Some variations of CNF allow one rule to have the
empty string (Λ) on the right-hand side (B -> Λ). This allows for optional
components in the generated strings.
2. No unit productions:
● A unit production is a rule where the right-hand side is just a single
non-terminal (A -> B). These can be eliminated by replacing them with the
original productions of B in all other rules.
3. No ε-productions (except in some variants):
● An ε-production is a rule where the right-hand side is empty (A -> ε). These
can be eliminated by rewriting all other rules to avoid using A directly and
introducing new non-terminals when necessary. However, some variations of
CNF allow one rule to have ε-production for flexibility.
4. No terminals on the right-hand side with more than one symbol:
● If a rule has multiple symbols on the right-hand side, including a terminal, you
need to introduce a new non-terminal to represent the combination of those
symbols. This ensures all terminals appear individually.
The following videos are more examples to help you better understand:
Video: Easy Theory, Chomsky Normal Form (CNF) Conversion Example
2
, lOMoARcPSD|44660598
Here are the steps to convert a Context-Free Grammar (CFG) to Chomsky Normal
Form (CNF):
1. Eliminate ε-productions (if not allowed):
○ If a rule has ε (the empty string) on the right-hand side (A -> ε), remove
it.
○ For each rule with A on the right-hand side (B -> ...A...), create new
rules with A's productions added, excluding A -> ε.
2. Eliminate unit productions:
○ If a rule has a single non-terminal on the right-hand side (A -> B),
replace it with B's productions. Iterate until no unit productions remain.
3. Eliminate terminals from RHS with more than one symbol:
○ If a rule has more than one symbol on the right-hand side, including a
terminal, introduce a new non-terminal:
■ A -> aBC -> aXC, X -> BC (replace terminal with new
non-terminal)
4. Break down long RHS (more than two non-terminals):
○ If a rule has more than two non-terminals on the right-hand side,
introduce new non-terminals to reduce it to two:
■ A -> BCD -> BX, X -> CD (create a chain of new non-terminals)
Key points:
● Apply these steps in the given order for a systematic conversion.
● Iterate steps as needed until all rules conform to CNF rules.
● Be mindful of the specific CNF variant you're using (e.g., allowing or
disallowing ε-productions).
PRACTISE QUESTIONS
NOV 2017
3
Downloaded by Gabriel Musyoka ()
2024
QUESTIONS AND
ANSWERS
FOR ASSISTANCE CONTACT
EMAIL:
, lOMoARcPSD|44660598
COS3701 VIDEO BASED STUDY
NOTES
Question 1:Context Free Grammars
Question 1A & 1B: Creation of a regular expression and sketching a Determinist
Finite Automaton (DFA)
Question A necessitates the creation of a regular expression, while Question B
entails sketching a Deterministic Finite Automaton (DFA). Ensure that you thoroughly
watch the videos below to grasp the underlying concepts.
Watch Videos 1-18 For a general introduction to concepts
Examples for designing regular expressions
Examples for sketching a Deterministic Finite Automaton (DFA)
After watching the videos attempt all question A and B in the provided question
papers.
Question 1C: Developing a CFG (Context free Grammar)
The two videos below are an introduction to CFGs. They explain what CFGs are and
give a brief introduction on how CFGs are constructed.
Context Free Grammar & Context Free Languages
Definition of CFG with an Example || Context Free Grammar || TOC || Theory of
Computation|| FLAT| CD
After watching the introduction videos u will now watch the videos below which have
a number of examples being explained. The more examples you watch the better you
will understand the concepts.
Examples 1
Examples 2
20 More Examples
Question 1D: Convert a CFG to Chomsky Normal Form (CNF)
For this section start by watching the videos below to understand the concepts and
then attempt the questions on your own.
Video: Simplification of CFG (Reduction of CFG)
Video: Simplification of CFG (Removal of Unit Productions)
Video: Simplification of CFG (Removal of Null Productions)
1
, lOMoARcPSD|44660598
Video: Chomsky Normal Form & CFG to CNF Conversion
Video: Example, Conversion of CFG to Chomsky Normal Form
Chomsky Normal Form (CNF) is a specific way of writing context-free grammars
(CFGs) with certain restrictions on the production rules. These restrictions make the
grammar simpler and easier to analyze, while still being able to generate the same
language as the original CFG.
Here are the key rules for a CNF CFG:
1. Two types of production rules:
● Binary branching: Each rule can either have two non-terminals on the
right-hand side (B -> CD) or a single terminal (B -> a). This restriction
simplifies how rules can be applied and combined.
● Empty string (optional): Some variations of CNF allow one rule to have the
empty string (Λ) on the right-hand side (B -> Λ). This allows for optional
components in the generated strings.
2. No unit productions:
● A unit production is a rule where the right-hand side is just a single
non-terminal (A -> B). These can be eliminated by replacing them with the
original productions of B in all other rules.
3. No ε-productions (except in some variants):
● An ε-production is a rule where the right-hand side is empty (A -> ε). These
can be eliminated by rewriting all other rules to avoid using A directly and
introducing new non-terminals when necessary. However, some variations of
CNF allow one rule to have ε-production for flexibility.
4. No terminals on the right-hand side with more than one symbol:
● If a rule has multiple symbols on the right-hand side, including a terminal, you
need to introduce a new non-terminal to represent the combination of those
symbols. This ensures all terminals appear individually.
The following videos are more examples to help you better understand:
Video: Easy Theory, Chomsky Normal Form (CNF) Conversion Example
2
, lOMoARcPSD|44660598
Here are the steps to convert a Context-Free Grammar (CFG) to Chomsky Normal
Form (CNF):
1. Eliminate ε-productions (if not allowed):
○ If a rule has ε (the empty string) on the right-hand side (A -> ε), remove
it.
○ For each rule with A on the right-hand side (B -> ...A...), create new
rules with A's productions added, excluding A -> ε.
2. Eliminate unit productions:
○ If a rule has a single non-terminal on the right-hand side (A -> B),
replace it with B's productions. Iterate until no unit productions remain.
3. Eliminate terminals from RHS with more than one symbol:
○ If a rule has more than one symbol on the right-hand side, including a
terminal, introduce a new non-terminal:
■ A -> aBC -> aXC, X -> BC (replace terminal with new
non-terminal)
4. Break down long RHS (more than two non-terminals):
○ If a rule has more than two non-terminals on the right-hand side,
introduce new non-terminals to reduce it to two:
■ A -> BCD -> BX, X -> CD (create a chain of new non-terminals)
Key points:
● Apply these steps in the given order for a systematic conversion.
● Iterate steps as needed until all rules conform to CNF rules.
● Be mindful of the specific CNF variant you're using (e.g., allowing or
disallowing ε-productions).
PRACTISE QUESTIONS
NOV 2017
3
Downloaded by Gabriel Musyoka ()
