COS3701 - Theoretical Computer Science III (COS3701)
Institution
University Of South Africa (Unisa)
Book
INTRODUCTION TO COMPUTER THEORY, 2ND ED
Want to cut your studying time in half??? If yes, then you definitely do not want to miss out on this wonderful opportunity. Contains all necessary concepts from the prescribed book with easy to understand explanations. Use this to get a distinction for this module.
COS3701 - Theoretical Computer Science III (COS3701)
All documents for this subject (44)
3
reviews
By: ajbrits • 2 year ago
By: ThabaMolo • 3 year ago
By: jamesdeanmanderson • 1 year ago
Seller
Follow
francoissmit
Reviews received
Content preview
Context Free Language (CFL)
CFL is a language generated by some Context Free Grammer(CFG)
CFGs
CFG formal definition:
Nonterminals are capital letters and terminals (since they can terminate, i.e end)
are small values.
Example:
So the general formulae is 𝑎𝑛 which is the language a*. Thus this CFG
generated the language a*. Remember a* means any certain number of a’s.
a* means any number of a’s. Can be 0 as well.
Note: -> is used in production and means ‘can be replaced by’ but the
double arrow means ‘çan develop into’.
Example:
,This is also the language a*. So both CFG’s in the 1st example and 2nd example
generated the language a*. This illustrated that more than 1 CFG can generate
the same language.
Example
The language generated by the CFG is the set of all possible strings of the
letters a and b except for the null string. Thus it is not (a+b)* because this
includes the null string.
In my own words: So we can start of with either making S aS or bS. Then again
we can replace that S with either aS or bS again for any number of times. Then
we can end it by replacing S with either a or b which makes the language all
possible strings of the letters a and b except for the null string.
Example
,From the start symbol S we can go to either X or Y. Notice then that X can only
produce the empty string .
Y can produce the same language as the previous example, i.e. all strings of a
and b excluding the empty string.
So adding then X production and Y productions then this CFG generates the
language (a+b)*. (a+b)* is any strings of a and b including the empty string .
Example
Also the word ab can be generated like this:
S=> aS
=>ab (S->b)
,Note the sequence of productions that is used to generate a specific word is not
unique. This also generated the language (a+b)*.
Note if we deleted the 3rd and 4th productions, the language generated would be
the same.
Example
So here we can replace X with a,b or NULL which us basically anything. Thus
we get ANYTHINGaaANYTHING which translates into (a+b)*aa(a+b)* which
is the language it generates.
Example *ask because this one is not allowed NULL values.
So X evaluates to any string that ends with an a. We must give it an ‘a’ to end it.
And Y evaluates to any string that starts with the letter ‘a’, because with Ya and
Yb the Y is in front. E.g. . To end Y we
must replace it with an ‘a’.
Thus this also generates the language as the previous example with 2 a’s in the
middle. i.e. (a+b)*aa(a+b)*.
Example:
,Note: We treat the non-terminals symbols BALANCED and UNBALANCED if
they were a single symbol.
Let us show that it can generate the word aababbab.
This is the language EVEN-EVEN, i.e. even number of a’s and b’s.
CFG’s can also generate non regular languages:
Example:
As you can see the S stays in the middle, because you are replacing the middle
section aREPLACEMENTb with a string that the S is in the middle, i.e. aSb. So
the S always stays in the middle.
This CFG generates the non-regular language
Éxample:
,This is the language EVENPALINDROME, i.e. it reads the same backwards as
forwards and it has an even amount of letters (with no letter at the centre)
See S is the middle and we always replace it with a letter that is the same as in
the left and right of the S. Thus it will yield the palindrome.
Example:
The ODDPALINDROME can be make from this CFG:
S->aSa
S->bSb
S->a
S->b
Note it is the same as the previous one except we will make the S the centre
letter.
e.g. S=>aSa
=>abSba
=>ababa (Here we havea central letter, but the rest reads the same
from left to right as right to left)
Now if we allow for the centre to be made into the empty string we will have
both ODDPALINDROME and EVENPALINDROME:
Example:
Generating the language
, See we can make infinite a’s but then we end the word with a b in the
middle.
Example:
So note the NT(nonterminal) A produces a, aS or bAA.
The NT B produces b, bS and aBB.
Generate a few words:
S=> aB
=> ab
S=> bA
=> baS
=>babA
=>baba
This generates the language EQUAL (equal number of a’s and b’s).
So the idea behind this is that if a word start with an ‘a’ then the rest of the
string contain 1 more b than a to make it equal.
,We now introduce the symbol | which means disjunction (or).
Example:
8(iv)
S-> aS|bX|Ʌ
X-> aY|bX|Ʌ
Y-> bS|Ʌ
Explanation. We need another route when we encounter a ‘b’. Then after we get
an ‘a’ on this route we must force a b otherwise we will get ‘baa’. So when we
get a ‘b’ from production 1 we force it on the X’s path. Then when we get an ‘a’
we send it to the 3rd production which forces a ‘b’ or an end.
To do this I started with S-> aS|bS|Ʌ and then knew I would have to alter bS
to get it to a new path. So I introduced a new NT symbol X. Then I went
X-> aX|bX|Ʌ and knew I have to alter aX so it can be on a new path. Thus I
introduced Y.
,Syntax Trees
We can sue trees with CFG’s to show how words can be formed.
Note that AA has 2 branches. Each single letter( symbol) has a branch.
, Reading from left to right we see that the word we have produces is bbaaaab
Example:
Show that the CFG can produce the string baaa using a syntax tree
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller francoissmit. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $5.51. You're not tied to anything after your purchase.
