Theory of Computation – Language of a DFA and Extended Transition Function

Language of a Deterministic Finite Automaton
A DFA defines a language. The set of all strings that result in a sequence of state transition from start state to an accepting state is the language defined by the DFA. The language is denoted as L(M) for a DFA M = (Q, Σ, δ, F q0), and is defined by

L(M) = {w:δ*(q0, w) is in F}.

Here δ* is the extended transition function. The language represented by a DFA is regular. In order to accept a language L, the FA has to accept all the strings in L and reject all the strings in L'(compliment of a language, i.e. strings not in the language).

Extended transition function
An extended transition function takes two arguments. The first argument is a state q and the second argument is a string w. It returns a state just like the transition function discussed in the previous tutorials. It can be defined as the state in which the FA ends up, if it begins in state q and receives string x of input symbols.
We define δ* recursively as follows:

  1. For any q ϵ Q, δ*(q, є) = q
  2. For any q ϵ Q and a ϵ Σ,
    δ*(q, ya) = δ(δ*(q,y), a)

For a string of length 1 δ*(q, a) = δ(q, a).

Question: Design a DFA for the language L = {w ϵ (a,b)*: nb mod 3 > 1}.
View Answer

Answer: nb represents the number of b in the string. nb mod 3 gives the remainder when nb is divided by 3. nb mod 3 > 1 implies that the remainder is 2. That means the number of b can be 2, 5, 8, …
Let M = (Q, Σ, δ, F q0) be the DFA
Σ = {a, b} is given.

For the automaton
Q = {q0, q1, q2}
F = {q2}

Question on designing and programming a DFA have been covered in the next tutorial.

advertisement
advertisement

Sanfoundry Global Education & Learning Series – 100+ Theory of Computation Tutorials.

If you wish to look at all Tutorials and their examples, go to Theory of Computation Tutorials.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.