# Theory of Computation ## Automata Conversion from NFA to DFA

The NFA to DFA conversion is based on subset construction. If a non-deterministic finite state machine consists of three states.                 Q = (q0, q1, q2,) The machine could form a power set on Q, which in given by 2Q . The procedure for finding whether a given string is accepted by the NFA, involves: Tracing…

A string 010 (starting with 01 and ending with 10 ) can be accepted through the path For any other string, the portion between starting 01 and ending 10 can absorbed by the state q2. Designing NFA step by step: Step – 1: Make initial state “q0”. Step -2: As  “q0” is initial state transition from…

## Differentiate between NFA and DFA

Difference between DFA and NFA SR.NO. DFA NFA 1 DFA stands for Deterministic Finite Automata NFA stands for Non-Deterministic Automata 2 More, if NFA contains Q states then the corresponding DFA will have <= 2Q states. NFA has fever number of states 3 DFA cannot use Empty String transition NFA can use Empty String transition….

## Design NFA to accept string containing the substring 0101

For reaching the final state q4 , from the start state q0 , a sub-string 0101 is required. Any string, containing a sub string 0101 will be accepted by the above NFA. The machine can remain in q0, for the portion of string before 0101. The machine can remain in q4 for the portion of…

## Design DFA which accept a binary number divisible by 3

Design of DFA divisibility – by – 3 tester for a binary number. A binary number is divisible by 3, if the remainder when divided by 3 will work out to be zero. We must device a mechanism for finding the final remainder. – We can calculate the running remainder based on previous remainder and…

## Design DFA that contain word ‘CAT’ using word ‘CHARIOT’

We are going to design a DFA that reads strings made up of letters in the word ‘CHARIOT’ and recognizes these strings that contain the word ‘CAT’ as a substring. Solution : Meaning of various states: q0 : Starting state. q1 : First character C of ‘CAT’ is the preceding character. q2 : First two…

## DFA for strings in which leftmost symbol differ from rightmost

We are going to design the DFA for the language, containing strings in which leftmost symbol different from rightmost symbol. Σ is given by {0,1}. This string should have following rules: The machine will end in the final state q2 if the leftmost symbol is 0 and the rightmost symbol is 1. The machine will…