For Assistance with other modules
Call or Whatsapp +27682021794
www.myassignments.co.za
COS3701
Assignment 02
2022
Due date
7 July 2022,
11:00 PM
UNIQUE NUMBER:
830417
+27682021794 www.myassignments.co.za [AUTHOR NAME]
, QUESTION 1
Build a DPDA to show that the language
is deterministic context free.
The smallest word in this language is when n= 3. This word is abababaaaba. All words in this
language start with three or more abs and end with one or more bas where there are always
two more abs than bas.
The trick to showing that this language is context free is to use the PDA to "match" the
occurrences of ab to the occurrences of ba which appear later in the string. We should also
take care of the fact that there have to be two more abs than bas but there has to be at least
one ba (and three abs).The aaa string in the middle is a separator and does not affect the
decision of whether or not the language is context free.
Our PDA can thus be outlined as
1. Read two instances of ab (but do nothing to the stack). These are the extra abs that we can
simply get rid of because we know there should be exactly two of them.
2. Read in one instance of ab (this matches with the one required ba).
3. Read in additional instances of ab and for each such instance push an X onto the stack.
Here we are essentially counting how many abs we have.
4. Read in aaa (but do nothing to the stack).
5. Read in the one required ba.
6. Read in instances of ba and for each instance pop an X off the stack. Here each ba is ticked
off against an ab that was read at the beginning of the string.
7. When all of the bas have been read then check that the input string and the stack are both
empty. We can now build a PDA to do this. The PDA is shown in diagram below.
2
Call or Whatsapp +27682021794
www.myassignments.co.za
COS3701
Assignment 02
2022
Due date
7 July 2022,
11:00 PM
UNIQUE NUMBER:
830417
+27682021794 www.myassignments.co.za [AUTHOR NAME]
, QUESTION 1
Build a DPDA to show that the language
is deterministic context free.
The smallest word in this language is when n= 3. This word is abababaaaba. All words in this
language start with three or more abs and end with one or more bas where there are always
two more abs than bas.
The trick to showing that this language is context free is to use the PDA to "match" the
occurrences of ab to the occurrences of ba which appear later in the string. We should also
take care of the fact that there have to be two more abs than bas but there has to be at least
one ba (and three abs).The aaa string in the middle is a separator and does not affect the
decision of whether or not the language is context free.
Our PDA can thus be outlined as
1. Read two instances of ab (but do nothing to the stack). These are the extra abs that we can
simply get rid of because we know there should be exactly two of them.
2. Read in one instance of ab (this matches with the one required ba).
3. Read in additional instances of ab and for each such instance push an X onto the stack.
Here we are essentially counting how many abs we have.
4. Read in aaa (but do nothing to the stack).
5. Read in the one required ba.
6. Read in instances of ba and for each instance pop an X off the stack. Here each ba is ticked
off against an ab that was read at the beginning of the string.
7. When all of the bas have been read then check that the input string and the stack are both
empty. We can now build a PDA to do this. The PDA is shown in diagram below.
2
