UnisaAssignHelp
COS3701
Assignment 2
Unique Number:
830417
, UnisaAssignHelp
Question 1
Build a DPDA to show that the language L = {(ab)naaa(ba)n−2 | n > 2} 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 three instances of ab (but do nothing to the stack). These are the leading abs that we can simply
get rid of because we know there should be exactly three of them.
2. Read in any other instances of ab and for each such instance push an X onto the stack. Here we are
essentially counting how many abs we have.
3. Read in aaa (but do nothing to the stack)
4. 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.
5. When a ∆ is popped from the stack then we know we have just read the ba that matches the three
abs that must be at the start of every string.
6. When the stack is empty then the DPDA must check that all of the bas have been read (ie there is no
additional input).
We can now build a PDA to do this.
The PDA is shown in Figure 1.
2
, UnisaAssignHelp
Figure 1: A DPDA to recognise L = {(ab)naaa(ba)n−2 | n > 2}
The six phases outlined above can be seen quite easily in the layout of the PDA.
3
COS3701
Assignment 2
Unique Number:
830417
, UnisaAssignHelp
Question 1
Build a DPDA to show that the language L = {(ab)naaa(ba)n−2 | n > 2} 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 three instances of ab (but do nothing to the stack). These are the leading abs that we can simply
get rid of because we know there should be exactly three of them.
2. Read in any other instances of ab and for each such instance push an X onto the stack. Here we are
essentially counting how many abs we have.
3. Read in aaa (but do nothing to the stack)
4. 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.
5. When a ∆ is popped from the stack then we know we have just read the ba that matches the three
abs that must be at the start of every string.
6. When the stack is empty then the DPDA must check that all of the bas have been read (ie there is no
additional input).
We can now build a PDA to do this.
The PDA is shown in Figure 1.
2
, UnisaAssignHelp
Figure 1: A DPDA to recognise L = {(ab)naaa(ba)n−2 | n > 2}
The six phases outlined above can be seen quite easily in the layout of the PDA.
3
