the formal specification of A. (8 marks) c) For

Question 1 Consider the finite automaton A given by the following transition diagram: a) Is A a Deterministic Finite Automaton (DFA) or a Nondeterministic Finite Automaton (NFA)? Justify your answer. (2 marks) b) Produce the formal specification of A. (8 marks) c) For all of the strings of length up to 5 over the alphabet Σ={a,b}, state the strings that will be accepted by A. Mention the string lengths whereby all strings are rejected. (5 marks) d) Use the GNFA algorithm to give a regular expression for the language recognized by A. Make sure to show all the steps involved to obtain maximal marks. (Use JFLAP to draw the diagrams) (10 marks)   Question 2 a) Convert the following NFA into DFA using the subset construction method. Show your entire process. (Use JFLAP to draw the diagrams. Use an empty node to indicate ∅) (15 marks) b) Prove that the following languages are not regular. (i) A={ωωω┤|ω∈{a,b}^ } (5 marks) (ii) B={ω∈{a,b}^ ∨ω=ω^R} (ω^R is the reverse of ω) (5 marks) Question 3 Let Σ={0,1} and L_a be the language of all strings that represent binary numbers that are not divisible by 4. L_b be the language of all strings that represent binary numbers that are odd. a) Produce regular expressions for L_a, L_b, (L_a∪L_b ). (7 marks) b) Produce ε-NFAs for L_a and L_b and then for (L_a∪L_b ) using the construction for the union of regular languages. (Use JFLAP to draw your diagrams) (7 marks) c) Produce a NFA that will determine whether any binary numbers (presented as a string) is divisible by 3. Describe the general idea of how such a finite automaton can be constructed to determine the divisibility of any integer n. (11 marks)   Question 4 Design a PDA for the following languages over Σ={0,1}. L_1={w┤|w=a^2n b^3n∨w=a^4n b^n forn=0,1,2,…} a) Explain the idea used. (6 marks) b) Design a state diagram for the PDA. (Use JFLAP to draw your diagrams) (6 marks) c) Using the concept discussed in part (a), discuss and also justify whether or not it is possible to construct a PDA for the following languages: L_2={w┤|w=a^n b^n c^n forn=0,1,2,…} L_3={w┤|w=a^n b^3n c^2m d^m forn,m=0,1,2,…} (6 marks) d) Design a CFG for the following transition diagram: (7 marks)

Leave a Reply

Your email address will not be published.