Computability

1. Consider the language given by the regular expression a*bc*. (a) Give a JFLAP implementation of a DFA that recognises this language, and test it on a suitable set of test data. (You need not include screen shots for each test screen, just give the trace of the DFAs behaviour on each.) (4 marks)
(b) Give a Type 3 grammar for this language and show how it produces those strings in your test data, which are accepted by your DFA. (4 marks)
S => => aA
=> bB
=> bC
=> b
A=> bB
=> bC
=> b
B=> aA
=> bB
=> bC
C=> b
=> aA
=> bB
=> cC
=> b
2. Consider the language {anbcn| n>= 1}.
(a) State the pumping lemma for regular languages and use it to show that this language is not regular. (4 marks)
Assume L={anbcn| n>= 1} is a regular language. Then pumping lemma holds.
Let p be the pumping length for L given by the lemma.
We choose S= apbcp {in L of length >= p}
Consider all cases s can be divided into x, y, z such that s= xyz satisfying conditions of the pumping lemma | y| > 0 and | xy| s= abic for all i >= 0, lets take i= 0
s= ab0c ==> s= ac
Therefore, L is not a regular language because s= ac does not satisfy the pumping lemma.
(b) Show that this language is context free by giving a CFG for this language. (3 marks)
L = {anbcn| n>= 1}
CFG = {V,{a, b, c}, P, S}
P:
S => abc
S => aSc

The lemma does not satisfy the language as a context-free grammar.
3. Consider the language {anb2ncn}.
(a) State the pumping lemma for context free languages and use it to show that this language is not context free. (7 marks)
L= {anb2nc}
CFG = { V, {a, b, c}, P, S }
P:
S => abbc
S => aSbbc
S => aSbc
The lemma does not satisfy the language as a context-free grammar.
(b) Give a JFLAP implementation of a Turing Machine that decides this language, and test it on a suitable set of test data.