Awesome q2a theme
0 votes
19 views

I need help in understanding the reasoning behind finding total number of states when positions of particular input is fixed from left hand side or right hand side. The Gate Overflow website shows the formula that for:

  1. nth position from the left side of the string is fixed , the number of states is  n+2
  2. nth position from the right side of the string is fixed, the number of states is  2n

I want to understand the logic behind this generalized formula. How did we come to this conclusion?

closed with the note: Question has been answered previously on the main website.
in Theory of Computation by (11 points)
closed ago by | 19 views
0
Firstly, thank you for sharing the link, I tried drawing certain DFA diagrams and understood for the case when nth position from the left side of the string is fixed , the number of states is  n+2.

But,

I could not deduce the same for the case when nth position from the right side of the string is fixed, the number of states is  2^n. Is there any way where you could show me via diagrams for certain number of n positions where we can generalize the concept of 2^n positions in DFA?
+1
Explainations are also provided, right ?
0
Yes, I found them in the "supported documents link" at the bottom of the post. I had overlooked that earlier. Thank you.
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users 2020 Aug 03 - 09
  1. Mellophi

    97 Points

  2. Ashutosh07091999

    69 Points

  3. prakhar2810

    7 Points

  4. Kushagra गुप्ता

    7 Points

  5. srestha

    7 Points

  6. sdutta

    6 Points

  7. kuldeep kumar07

    6 Points

  8. toppoavinash

    6 Points

  9. Shoaib_Ahmed

    6 Points

  10. prashastinama

    6 Points

Weekly Top User (excluding moderators) will get free access to GATE Overflow Test Series for GATE 2021
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Aug 2020
  1. Mellophi

    103 Points

  2. Ashutosh07091999

    72 Points

  3. Shaik Masthan

    13 Points

  4. srestha

    9 Points

  5. Unnayan kumar

    8 Points

  6. prakhar2810

    7 Points

  7. Sourav Kar

    7 Points

  8. anurag_yo

    7 Points

  9. Kushagra गुप्ता

    7 Points

  10. sdutta

    6 Points

7,711 questions
1,823 answers
11,131 comments
95,090 users