Question

BRING 4 CHALLENGING QUESTION WITH SOLUTION FOR THE FOLLOWING QUESTION

1. Using MOD function with concept explanation for DFA ( DFA WITH MODE FUNCTION)

Please do not upload simple question and question that available on the internet .....it must be challenging

Thank you

Answer 1

Question 1

Construct DFA for the language L = {w | w ∈ {a,b}* and Na(w) mod 3 = Nb (w) mod 3}.

Note:  L={w | Na(w) = Nb(w)mod 3} which means all string contain modulus of count of a’s equal to modulus of count of b’s by 3.

Eg:

Input: a a b b b
Output: NOT ACCEPTED
Because n = 2, m=3 (2 mod 3! = 3 mod 3)

Input: a a b b
Output: ACCEPTED
Because n = 2, m = 2 (2 mod 3 = 2 mod 3)

Solution:(Step by step)

• Construct FA for {w | w {a, b}} and Na = 0 mod 3 means having a’s as a multiple of 3.
• Construct FA for {w | w {a, b}} and Nb = 0 mod 3 means having b’s as a multiple of 3.
• Concatenate the two FA and make single DFA using Concatenation process in DFA.
• Making state as final state which accepts the equal modulus count for a’s and b’s.

DFA State Transition Diagram:

Question 2

Design a deterministic finite automata (DFA) for accepting the language

Regular expression for above language L is,

Input:  a a b b b           
Output:  ACCEPTED
// n = 2 (even) m=3 (>=1)

Input:  a a a b b b         
Output:  NOT ACCEPTED
 // n = 3 (odd), m = 3

Solution:

1. Construct FA for means having even number of a’s.
2. Construct FA for means having any number of b’s greater than one.
3. Concatenate the two FA and make single DFA.

Any other combination result is the rejection of the input string.

DFA State Transition Diagram:

Question 3:

Construct a DFA which accept the language L = {aⁿb^m | n > =1, (m) mod 3 = 1}.

When it comes to solution always keep the below point:

" which means any no of elements, and
 which means any no of elements greater than 1."

Input: a a b b b           
Output: NOT ACCEPTED
// n = 2 (>=1), m=3 ((3) mod3 != 1)

Input: a a a b        
Output: ACCEPTED
 // n = 3 (>=1), m = 1 ((1) mod 3= 1)

• Construct FA for means having any number of a’s greater than one.
• Construct FA for means having exactly
• Construct FA for means having b’s equal to multiple of 3 .
• Concatenate the three FA and make single DFA. Always maintain the order of a, b and c.

DFA State Transition Diagram:

Question 4:

Construct a DFA to accept all strings which satisfy w(x)mod 5 =2 .

Lets go directly to the transition diagram now:

State	0(Input alphabet)	1(Input aphabet)
q0	q0	q1
q1	q2	q3
*q2	q4	q0
q3	q1	q2
q4	q3	q4

Now by above state table draw DFA and make q2 as a final state bcz    w(x)mod5=2

The state diagram

Above mentioned some of the challenging questions in the field of NFA which I felt good. Also all are related with mod.