CSCI435 Home Assignment 1Solved

35.00 $ 17.50 $

Category:
Click Category Button to View Your Next Assignment | Homework

You'll get a download link with a: . zip solution files instantly, after Payment

Description

5/5 - (1 vote)

 

Q1. [25] For S = {a, b}, construct the minimal DFA that accept the language consisting of

  •  all strings with an even number of a’s and an odd number of b’s.
  • every ‘aa’ is followed immediately by a ‘b’. For example, the strings aab, aaba, aabaabbaab are in the language, but aaab and aabaa are not. Construct a DFA with 4 states.
  •  L = {w | ( na(w) – nb(w) ) mod 3 = 0 }. Construct a DFA with 3 states.

Q2. Show that the language L = { an | n ³ 0, n ¹ 3 } is regular.

Q3.  For the language L = {an | n ³ 1 } È {bmak | m ³ 0, k ³ 0}

  •  Construct an NFA with three states that accepts L.
  •  Can you construct an NFA with the fewer states that accepts L? If so, construct it; otherwise, justify why your NFA in 1) is the minimal NFA.

Q4.  For a given NFA in the figure,

  • Give a language L that is accepted by the NFA. Describe L in the proper mathematical format, not in the verbal English description.  g.) L = { an | n ³ 0, n ¹ 3 }
  • Find a DFA that accepts the complement of the language defined by the NFA, i.e. .

Q5. Construct an NFA with the minimum number of states that accepts

L = { an | n ³ 0 } È { bna | n ³ 1 }.

Q6.  Convert the NFA defined by the transitions below with the initial state q0 and the final state q2 into an equivalent DFA.  Draw the transition graph of the DFA.

d(q0, a) = { q0, q1 },    d(q1, b) = { q1, q2 },    d(q2, a) = { q2 },    d(q1, l) = { q1, q2 }.

Q7.  For a given language, L = { anb | n ³ 1 } È { bna | n ³ 1},

  •  Construct a minimal DFA with the minimum number of states that accepts L.
  • Prove that your DFA in 1) is minimal. Hint: Check if any pair of the states are indistinguishable to be merged in the same class so that the number of states are minimized

Q8.  Prove or disprove the following conjecture:  If L is regular, so is LR.

If it is true, construct a NFA MR s.t. L(M’) = LR , from a NFA M that accepts L, i.e. L(M) = L. Then, show that L(M’ ) = LR .

Otherwise, give a counter example.

 

 

 

  • HW1-cbosfy.zip