how many different dfa can be designed | TOC | THEORY OF COMPUTATION | AUTOMATA | part-23
ฝัง
- เผยแพร่เมื่อ 25 ส.ค. 2024
- 🔥 Want to get placed? Enroll to this SuperSet course for TCS NQT and get placed:
tiny.cc/yt_supe...
✅ Sanchit Sir is taking live class daily on Unacademy Plus for Complete Syllabus of GATE 2022:
🔴 Use Referral code: KGYT to get minimum 10% discount on registration fee
🚀 Link for subscribing to the course is: tiny.cc/yt_unac...
🌟 For all our latest courses launched visit:
🆕Knowledge Gate website: tiny.cc/yt_kgwe...
▶️Download Knowledge Gate app: Play Store Link: tiny.cc/yt_KgApp
🌟Enroll in Certificate Courses by Knowledge GATE:
✅ Python Programming: tiny.cc/yt_pyth...
✅ Programming for Placement :tiny.cc/yt_prog...
✅ Competitive Programming: tiny.cc/yt_comp...
👉 Join our Telegram group for :
📝Free classes by Sanchit Jain Sir on Unacademy daily: t.me/KGgatefre...
📝All Placement related update: t.me/joinchat/...
👉 Join the whatsapp group via Invite Link:
1. chat.whatsapp....
2. chat.whatsapp....
3. chat.whatsapp....
4. chat.whatsapp....
5. chat.whatsapp....
👉 Follow us on Social media to get all updates:
📸 Instagram - tiny.cc/yt_KgIn...
👥 Facebook page and give us a 5 star review with comments - tiny.cc/fb_kg
📝 Quora - tiny.cc/quora_kg
🌎 Give us a 5 star review with comment on Google - tiny.cc/google_kg
👉 Subscribe Knowledge Gate English Channel tiny.cc/knowled...
👉 Subscribe Our Other Channel Sab Kuch tiny.cc/sabkuch_kg
▶️ Checkout other videos by Knowledge GATE:
1) Digital Electronics: tiny.cc/digital_kg
2) Discrete Mathematics (Graph Theory): tiny.cc/graph_t...
3) Discrete Mathematics (Group Theory): tiny.cc/group_t...
4) Discrete Mathematics (Set Theory): tiny.cc/set_the...
5) Discrete Mathematics (Function): tiny.cc/functio...
6) TCS NQT Preparation by Yash Jain Sir: tiny.cc/yt_tcsn...
7) Motivation Series by Sanchit Sir: tiny.cc/yt_moti...
8) Data Structures by Vinay Sir: tiny.cc/ds_kg
9) Algorithm by Vinay Sir: tiny.cc/algorit...
10) Compiler: tiny.cc/compile...
11) TOC: tiny.cc/toc_kg
12) Mathematics Calculation Short Tricks: tiny.cc/maths_t...
13) Interview Preparation: tiny.cc/intervi...
14) Programming for Placements by Vinay Sir : tiny.cc/yt_prog...
15)Placement Preparation by Yash Jain Sir : tiny.cc/yt_plac...
16) Job Notification: tiny.cc/job_new...
17)) Unacademy: tiny.cc/unacade...
18) How to be Successful / Career Guidance -tiny.cc/careerg...
okay so if we take the transition function to be such that q0 forms a self loop for both of the cases of a and b, then in that case we won't have q1 in the dfa and hence, the no of states will decrease to just the one. This violates the condition that you mentioned earlier where it was given that the no of states is fixed. The total no of DFAs possible in that case should be 16 - (No of DFAs with 1 state) = 16-14 = 12.
According to the definition of DFA " machine must be complete in nature" ie every state should be able to handle every alphabet. According to you, there won't be any transition from q0 to q1 which violates the definition of dfa as in the question it is specified that there must be two states.
@adityakrishna
I have the same doubt.
Did you get the answer for it?
what a explanation!!!
How many two state DFA'S are possible with designated initial state and designated final state over {a,b)
Please explain.
Thank you Sir.
Till now whatever video on TOC u have uploaded, I understood it . I dont' have TOC at my MCA level and feeling hard to learn TOC. But your videos are making it easy. Thanks
awesome sir thanks for these videos please keep uploading on different tricky and important topics
thanks for loading this video sir
...
sir in this we took all possible combinations as taking q0 as initial state we can have 4 more combination taking q1 as initial state now by this we also get 64 more combination so total become 128 combination of dfa na sir .. please clear this doubt .
Hello Sir. I've been watching each video of Yours. Your videos have helped me understanding some concepts I had less confidence in. Please upload Videos on "I/O Interfacing In Computer organisation"..I Know the theory part But Can't Solve Numerical questions of that Topic. Please, If possible, Upload soon. Thank You!!
Sir plz explain how 16 states are possible .. If we include all the states with 00 as initial transition then it would not be a complete dfa..
sym a | b
q0. q0 | q0
q0. q0 | q1
q0. q1 | q0
q0. q1 | q1
Similarly for q1 we'll get 4 combinations, totally 16.
@@crazeeealgorithms3236 I am still not able to get it can you please write for the q1 state. It would be very helpful
@@sudiptodas3896 drive.google.com/file/d/1w2kcNroOkj6Hx9uda5JhbrtCa706ZY_J/view?usp=drivesdk
@@sudiptodas3896 you can view it now
@@crazeeealgorithms3236 thanks a lot..
Sir, In previous videos you mentioned there must be atleast one final state but in this video, you consider DFA with zero final state. How is this possible.
Zero final states is possible, it means this machine does not accept any string.
@@shatadruroychowdhury6319 then what's the use of that machine?
hello sir, i have a general request. At the end of your every video , there comes a custom ad asking us to click for watching other of your play-lists. why is it Non-cancellable? It irritates the student when it suddenly pops and makes us miss some important last seconds of question ,and we can't even close it! :|
Sir, in the formula - 2^m * m^(m*n)....
What is 2?
there is two state(a,b),,thats why here use 2^m*n combination
'm' is the number of states (like there are 2 states in the given example, q0 & q1).
'n' is the number of input symbols (like there are 2 in the above example, 'a' & 'b').
The 2 over here is to cover all the possible final states, like if there are 2 states then the possible combinations of final states are: {}, {q0}, {q1}, {q0,q1}, which is same as the power set.
As each state has 2 possible outcomes, either it can be a final state or it isn't the final state, hence for every state we multiply 2, therefore 2^m possible combinations of final states.
Thanks
If qo takes (a,b) and returns to qo and q1 takes (a,b) and returns to q1, then how can we say that it is a dfa?