• Home
  • Subscribe
  • Contribute Us
    • Share Your Interview Experience
  • Contact Us
  • About
    • About CSEstack
    • Campus Ambassador
  • Forum & Discus
  • Tools for Geek
  • LeaderBoard
CSEstack

What do you want to Learn Today?

  • Programming
    • Tutorial- C/C++
    • Tutorial- Django
    • Tutorial- Git
    • Tutorial- HTML & CSS
    • Tutorial- Java
    • Tutorial- MySQL
    • Tutorial- Python
    • Competitive Coding Challenges
  • CSE Subject
    • (CD) Compiler Design
    • (CN) Computer Network
    • (COA) Computer Organization & Architecture
    • (DBMS) Database Management System
    • (DS) Data Structure
    • (OS) Operating System
    • (ToA) Theory of Automata
    • (WT) Web Technology
  • Interview Questions
    • Interview Questions- Company Wise
    • Interview Questions- Coding Round
    • Interview Questions- Python
    • Interview Questions- REST API
    • Interview Questions- Web Scraping
    • Interview Questions- HR Round
    • Aptitude Preparation Guide
  • GATE 2022
  • Linux
  • Trend
    • Full Stack Development
    • Artificial Intelligence (AI)
    • BigData
    • Cloud Computing
    • Machine Learning (ML)
  • Write for Us
    • Submit Article
    • Submit Source Code or Program
    • Share Your Interview Experience
  • Tools
    • IDE
    • CV Builder
    • Other Tools …
  • Jobs

Construct DFA | Number of a is Odd & Number of b is Not Divisible by 3

Aniruddha Chaudhari/40746/1
GATE CS IT QuestionsTheory of Automata

How to construct DFA to accept a language L={Strings in which the total number of ‘a’ is an odd and total number of b’s is not divisible by 3}?

This is a complicated question to construct DFA. To solve this kind of questions use divide and conquer strategy.

Steps to Construct DFA:

  • Divide this problem into two parts.
    Construct the DFA for a string which has the total number of ‘a’ is odd.
    Construct the DFA for a string which has the total number of b’s is not divisible by 3.
  • Once done, combine both the DFA automata.
  • To get minimal DFA, remove any dead/unwanted/unreachable/duplicate state from the DFA.

Construct DFA for a string which has a total number of ‘a’ is odd:

Constructing a DFA for total number of a's is odd

This is a simple DFA with 2 states. One is starting state and other is the final state. It accepts all the string which have the occurrence of odd numbers of a.

There is no change in the transition state for the occurrence of b. So occurrence ob b forms the loop on the same state.

Construct DFA for a string which has a total number of ‘b’ is not divisible by 3:

To make it simple, follow these two steps

Step 1: construct DFA that accepts the string which has the total number of b’s is divisible by 3.

Step 2: Take the negation of constructed automata. This is possible by changing all the non-final states to final states and all final states to non-final states.

construct DFA for string with total number of b's is divisible by 3

Construct Final DFA:

Combine both the above automata to construct DFA that accepts all the strings with the total number of ‘a’ is an odd & total number of b’s is not divisible by 3.

Take the combinations of all the states from both DFAs. So there are 8 states (4*2) which include 3 final states.

Construct DFA Total Number of a's is Odd & Number of b's is not Divisible by 3

 

Find minimal DFA:

Remove all the unwanted stated from DFA. Unwanted states can be which are not reachable from starting state, a dead state which does not lead anywhere. Combine all the states that have all transitions to the same states.

In this case, there are not any unwanted states in DFA. Also, don’t have any common states to be combined.

This answer is elaborated based on the question asked in GATE CSE Facebook Community for GATE aspirants.

To construct DFA, it needs to practice. You can refer to the book Theory of Computation by Ullman to practice answering such kind of questions.

 

Note for GATE aspirants: If you are solving this question in GATE exam, it is time-consuming. In GATE, there are MCQ questions. There will be four answers with four DFA automata. Instead of constructing DFA, try to find out the answer by matching language given in the question with given automata in the answers.  (Reference: How to prepare for GATE)

Aniruddha Chaudhari
I am complete Python Nut, love Linux and vim as an editor. I hold a Master of Computer Science from NIT Trichy. I dabble in C/C++, Java too. I keep sharing my coding knowledge and my own experience on CSEstack.org portal.

Your name can also be listed here. Got a tip? Submit it here to become an CSEstack author.

Comments

  • Reply
    Jenny
    October 18, 2018 at 7:49 am

    Can you construct a Regular expression where some element is not divisible by 3 {a,b}

Leave a Reply Cancel reply

Interview Questions



You can share your interview experience.

Subscribe for FREE Newsletter

Do you want me to send you programing updates for FREE?

Subscribe below…

© 2022 – CSEstack.org. All Rights Reserved.

  • Home
  • Subscribe
  • Contribute Us
    • Share Your Interview Experience
  • Contact Us
  • About
    • About CSEstack
    • Campus Ambassador
  • Forum & Discus
  • Tools for Geek
  • LeaderBoard