JFLAP Implementation of a DFA - Essay Example

1. Consider the language given by the regular expression a*bc*.
(a) Give a JFLAP implementation of a DFA that recognizes this language, and tests it on a suitable set of test data. (You need not include screenshots for each test screen, just give the trace of the DFA's behavior 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| <= p
• For s= a1bc1 ==> 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 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 tests it on a suitable set of test data. Read More