This paper consists of 7 pages. Hierdie vraestel bestaan uit 7 bladsye.
Instructions / Instruksies: 1.
Answer all questions. Beantwoord al die vrae.
2.
All rough work must be done in your answer book. Alle rofwerk moet in u antwoordboek gedoen word.
3.
The mark for each question is given in brackets next to the question. Die punt vir elke vraag word tussen hakies langs die vraag aangedui.
4.
Unless otherwise specified, all languages in the questions are defined over the alphabet ∑ = {a,b}. Tensy anders gemeld is alle tale in die vrae gedefinieer oor die alfabet ∑ = {a,b}. ALL THE BEST!! STERKTE!!
[TURN OVER] [BLAAI OM]
2
COS2601 October / November 2014 Oktober / November 2014
SECTION 1 / AFDELING 1 REGULAR EXPRESSIONS AND LANGUAGES / REGULIERE UITDRUKKINGS EN TALE [20 marks / punte] QUESTION 1 / VRAAG 1 (a)
[10]
Let S = {aa, baba, bba, ab}. For each of the following strings, state whether or not it is a word in S*. Justify your answer. Laat S = {aa, baba, bba, ab}. Vir elk van die volgende stringe, dui aan of dit ‘n woord in S* is of nie. Motiveer u antwoord. (i) bbaabbaba (ii) abbbaabaa (4)
(b)
Let S = {a, bb}. Write down all the words with four or fewer letters that belong to S*. Laat S={a, bb}. Skryf al die woorde met vier of minder letters neer wat aan S* behoort.
(2)
(c)
Provide an example of a set S such that S* has exactly as many four letter words as five letter words. Gee ‘n voorbeeld van ‘n versameling S sodanig dat S* net soveel vier-letter woorde as vyf-letter woorde het. (2)
(d)
Provide an example of two sets S and T of strings, with S ≠ T, such that: S* T* = (S T)* Gee ‘n voorbeeld van twee versamelings S en T van stringe sodanig dat S ≠ T en S* T* = (S T)*
(2)
QUESTION 2 / VRAAG 2 (a)
[10]
Consider the regular expression: Beskou die reguliere uitdrukking: (a + b)*ab(a + b)* + b*a* Describe in words the language generated by the presented regular expression. Besktyf in woorde die taal wat deur die gegewe reguliere uitdrukking voortgebring word.
(3)
(b)
Provide a regular expression that generates the language consisting of all words of even length. Gee ‘n reguliere uitdrukking wat die taal genereer wat bestaan uit alle woorde van ewe lengte. (2)
(c)
Provide a regular expression that generates the language consisting of all words without a double b. Thus the bb-substring should not occur. Gee ‘n reguliere uitdrukking wat die taal genereer wat bestaan uit alle woorde waar die bbsubstring nie voorkom nie. (3)
[TURN OVER] [BLAAI OM]
3
(d)
Does the regular expression Genereer die reguliere uitdrukking
COS2601 October / November 2014 Oktober / November 2014
(b + Λ) (ab)*(aab)*(a + Λ)
generate the language of all words where the aaa-substring does not occur? Justify your answer. die taal van alle woorde waar die aaa-substring nie voorkom nie? Motiveer u antwoord. (2)
SECTION 2 / AFDELING 2 RECURSIVE AND INDUCTIVE PRINCIPLES / REKURSIEWE EN INDUKTIEWE BEGINSELS [20 marks / punte] QUESTION 3 / VRAAG 3
[10]
A recursive definition for the language ODDnotBB defined over the alphabet Σ = {a,b} should be compiled. ODDnotBB consists of all words that are of odd length and that do not contain the bb-substring. ‘n Rekursiewe definisie vir die taal ODDnotBB gedefineer oor die alfabet Σ = {a,b} moet saamgestel word. ODDnotBB bestaan uit alle woorde van onewe lengte wat nie die bb-substring bevat nie. Provide Gee
(a)
(b)
(c)
(d)
an appropriate universal set, ‘n toepaslike universele versameling,
(1)
the generator(s) of ODDnotBB, die voortbringer(s) van ODDnotBB,
(2)
an appropriate function on the universal set, and then ‘n toepaslike funksie op die universele versameling, en
(1)
use these concepts to write down a recursive definition for the language ODDnotBB. gebruik dan hierdie begrippe om ‘n rekursiewe definisie vir die taal ODDnotBB neer te skryf. (6)
QUESTION 4 / VRAAG 4 (a) (b) (c)
[10]
Provide a recursive definition of the set P of all integers greater than 0, Gee ‛n rekursiewe definisie van die versameling P van alle heelgetalle groter as 0,
(1)
formulate the associated induction principle, and formuleer die gepaardgaande induksiebeginsel, en
(2)
then apply this induction principle to prove that: pas dan die induksiebeginsel toe om te bewys dat:
10 + 20 + 40 + ... + 5(2) n = 10(2 n − 1)
(7) [TURN OVER] [BLAAI OM]
4
COS2601 October / November 2014 Oktober / November 2014
SECTION 3 / AFDELING 3 REGULAR LANGUAGE ACCEPTORS / REGULIERE TAAL AANVAARDERS [20 marks / punte] QUESTION 5 / VRAAG 5
[10]
Build an FA (finite automaton) that accepts the language L consisting of all words that: • have a length divisible by 3 without a remainder and • end in the bb-substring L is defined over the alphabet ∑ = {a,b}. Bou ‘n FA (finite automaton (eindige outomaat)) wat die taal L aanvaar wat bestaan uit alle woorde met: • ‘n lengte wat deelbaar is deur 3 sonder ‘n res en • wat met die bb-substring eindig L is gedefinieer oor die alfabet ∑ = {a,b}.
QUESTION 6 / VRAAG 6 (a)
[10]
Build an FA that accepts the same language as the FA below, but that consists of fewer states: Bou 'n FA wat dieselfde taal aanvaar as die volgende FA, maar wat uit minder toestande bestaan: (6) 3 b a
b 1-
a
2
a, b
b a
(b)
4+
Build a TG (Transition Graph) with only two states that accepts exactly the same language as the FA in (a). Bou 'n TG (transition graph, oorgangsgrafiek) met net twee toestande wat dieselfde taal as die FA in (a) aanvaar. (4)
[TURN OVER] [BLAAI OM]
5
COS2601 October / November 2014 Oktober / November 2014
SECTION 4 / AFDELING 4 APPLICATION OF ALGORITHMS WHITHIN KLEENE’S THEOREM / TOEPASSING ALGORITMES BINNE KLEENE SE STELLING [20 marks / punte] QUESTION 7 / VRAAG 7
[10]
By applying Kleene’s theorem, find a regular expression that generates the language accepted by the following TG (transition graph). Show all the steps. Deur Kleene se stelling toe te pas, vind ‘n reguliere uitdrukking wat die taal genereer wat deur die volgende TG (transition graph, oorgangsgrafiek) aanvaar word. Dui al die stappe aan.
3 aa a b
aa,bb 1-
2 5+
bb a,b
4+
[TURN OVER] [BLAAI OM]
6
COS2601 October / November 2014 Oktober / November 2014
QUESTION 8 / VRAAG 8
[10]
Let L1 be a language defined by the regular expression r1. Consider FA1 that accepts all the words of L1: Laat L1 ‘n taal wees gedefinieer deur die reguliere uitdrukking r1. Beskou FA1 wat al die woorde van L1 aanvaar: FA1
b
-x1
a a
b
x2 b b
x4
b
a +x3
a Build another FA that accepts all the words of the language L1* defined by r1*. (Do not formulate a regular expression.) Bou nog ‘n FA wat al die woorde in die taal L1*, wat deur r1* gedefinieer word, aanvaar. (Moenie ‘n reguliere uitdrukking formuleer nie.)
SECTION 5 / AFDELING 5 NONREGULAR LANGUAGES / NIE-REGULIERE TALE [10 marks / punte] QUESTION 9 / VRAAG 9
[10]
Use the Pumping Lemma with length to prove that the following language is non-regular: Gebruik die Pomplemma met lengte om te bewys dat die volgende taal nie-regulier is: L = { bn c10 an c10 n = 1, 2, 3, ... }.
[TURN OVER] [BLAAI OM]
7
COS2601 October / November 2014 Oktober / November 2014
SECTION 6 / AFDELING 6 DECIDABILITY / BESLISBAARHEID FAs WITH OUTPUT / FAs MET AFVOER [10 marks / punte] QUESTION 10 / VRAAG 10 (a)
[10]
Describe a method whereby it can be determined whether a language, accepted by a certain FA, consists of an infinite number of words. Beskryf ‘n metode waardeur bepaal kan word of ‘n taal wat deur 'n gegewe FA aanvaar word, uit 'n oneindige aantal woorde bestaan. (5)
(b)
Explain how Mealy machines differ from Moore machines. Verduidelik hoe Mealy masjiene van Moore masjiene verskil.
© UNISA 2014
(5)
