Theoretical Computer Science III
COS3701
Assignment 2
School of Computing
This tutorial letter contains important information
about your module.
BARCODE
, Question 1 10
Find CFGs for all words that do not have the substring aba over the alphabet ∑
= {a b}.
Solution
The simplest manner by which the required CFG can be obtained will be by
drawing an FA which accepts the required language and then applying Theorem
21 of Cohen.
Note that you would not lose any marks if you have present a correct CFG
without drawing an FA.
However, for exam purposes it is recommended that if a CFG, which generates
a regular language, is requested that you should draw an FA which accepts the
required language and apply Theorem 21 in order to deduce the requested
CFG.
Consider the FA shown below and convince yourself that it will recognise all and
only words from L. Do this by testing various words from L (e.g. abba, baba,
etc.) Note that this is probably not the only FA which could be constructed to
recognise words in this language.
We apply Theorem 21 as follows:
Step 1 The nonterminals in the CFG will be all the names of the states in the FA
with the start state renamed S.
Names in the form of alphabet letters should be provided to the respective
states of our FA. We use capital letters to label the respective states of our FA
as these labels will become the respective non-terminals of our CFG. It is
recommended that the start state of the FA, to be converted to a CFG, should
be labelled S.
COS3701
Assignment 2
School of Computing
This tutorial letter contains important information
about your module.
BARCODE
, Question 1 10
Find CFGs for all words that do not have the substring aba over the alphabet ∑
= {a b}.
Solution
The simplest manner by which the required CFG can be obtained will be by
drawing an FA which accepts the required language and then applying Theorem
21 of Cohen.
Note that you would not lose any marks if you have present a correct CFG
without drawing an FA.
However, for exam purposes it is recommended that if a CFG, which generates
a regular language, is requested that you should draw an FA which accepts the
required language and apply Theorem 21 in order to deduce the requested
CFG.
Consider the FA shown below and convince yourself that it will recognise all and
only words from L. Do this by testing various words from L (e.g. abba, baba,
etc.) Note that this is probably not the only FA which could be constructed to
recognise words in this language.
We apply Theorem 21 as follows:
Step 1 The nonterminals in the CFG will be all the names of the states in the FA
with the start state renamed S.
Names in the form of alphabet letters should be provided to the respective
states of our FA. We use capital letters to label the respective states of our FA
as these labels will become the respective non-terminals of our CFG. It is
recommended that the start state of the FA, to be converted to a CFG, should
be labelled S.
