EXTENSIVE! COS3701 Summary (Theoretical Computer Science III)

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