Tentamen (uitwerkingen)

COS3701 Exam pack 2024 (Theoretical Computer Science III) Questions and answers

2 keer verkocht

Vak
Theoretical Computer Science III

Instelling
University Of South Africa

COS3701 Exam pack 2024 (Theoretical Computer Science III) Questions and answers With accurate answers and assurance that they are in the exam

[Meer zien]

Voorbeeld 4 van de 67 pagina's

Bekijk voorbeeld

Geupload op 16 september 2024
Aantal pagina's 67
Geschreven in 2024/2025
Type Tentamen (uitwerkingen)
Bevat Vragen en antwoorden

cos3701

Instelling
University of South Africa
Vak
Theoretical Computer Science III

Volgen

gabrielmusyoka940

Lid sinds 1 jaar 644 documenten verkocht

€2,39

In winkelwagen

Opslaan

100% tevredenheidsgarantie
Direct beschikbaar na je betaling
Lees online óf als PDF
Geen vaste maandelijkse kosten

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
Deﬁnition 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: Simpliﬁcation of CFG (Reduction of CFG)
Video: Simpliﬁcation of CFG (Removal of Unit Productions)
Video: Simpliﬁcation 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 ()

Dit zijn jouw voordelen als je samenvattingen koopt bij Stuvia:

Bewezen kwaliteit door reviews

Studenten hebben al meer dan 850.000 samenvattingen beoordeeld. Zo weet jij zeker dat je de beste keuze maakt!

In een paar klikken geregeld

Geen gedoe — betaal gewoon eenmalig met iDeal, Bancontact of creditcard en je bent klaar. Geen abonnement nodig.

Focus op de essentie

Studenten maken samenvattingen voor studenten. Dat betekent: actuele inhoud waar jij écht wat aan hebt. Geen overbodige details!

Veelgestelde vragen

Wat krijg ik als ik dit document koop?

Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.

Tevredenheidsgarantie: hoe werkt dat?

Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.

Van wie koop ik deze samenvatting?

Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper gabrielmusyoka940. Stuvia faciliteert de betaling aan de verkoper.

Zit ik meteen vast aan een abonnement?

Nee, je koopt alleen deze samenvatting voor €2,39. Je zit daarna nergens aan vast.

Is Stuvia te vertrouwen?

4,6 sterren op Google & Trustpilot (+1000 reviews)

Afgelopen 30 dagen zijn er 66184 samenvattingen verkocht

Opgericht in 2010, al 15 jaar dé plek om samenvattingen te kopen

Start met verkopen

Tentamen (uitwerkingen)

COS3701 Exam pack 2024 (Theoretical Computer Science III) Questions and answers

Document informatie

Onderwerpen

Geschreven voor

Verkoper

Ontvangen beoordelingen

Voorbeeld van de inhoud