EduLadder(ELADR) - CRYPTO

This is designed to incentify community members as a proof of contribution token.


Using this You can,Buy courses,Reward others and exchange for real money.


WHITE PAPER COURSES

Real Problems! Real Experts!

Join Our Telegram Channel !


The Eduladder is a community of students, teachers, and programmers. We help you to solve your academic and programming questions fast.
In eduladder you can Ask,Answer,Listen,Earn and Download Questions and Question papers.
Watch related videos of your favorite subject.
Connect with students from different parts of the world.
Apply or Post Jobs, Courses ,Internships and Volunteering opportunity. For FREE
See Our team
Wondering how we keep quality?
Got unsolved questions? Ask Questions

Design-and-Analysis-of-Algorithms-Subject-Code--10CSL47-Lab-Manual-PROGRAM-11-->View question


Asked On2017-06-07 08:27:04 by:prajwalamv

Taged users:
arunwebber

Likes:
Be first to like this question

Dislikes:
Be first to dislike this question
Talk about this  Like  Dislike
View all questions
Answers
DFA Minimization using Equivalence Theorem:
If X and Y are two states in a DFA, we can combine these two states into {X, Y} if they are not distinguishable. Two states are distinguishable, if there is at least one string S, such that one of δ (X, S) and δ (Y, S) is accepting and another is not accepting. Hence, a DFA is minimal if and only if all the states are distinguishable.
Step 1 − All the states Q are divided in two partitions − final states and non-final states and are denoted by P0. All the states in a partition are 0th equivalent. Take a counter k and initialize it with 0.
Step 2 − Increment k by 1. For each partition in Pk, divide the states in Pk into two partitions if they are k-distinguishable. Two states within this partition X and Y are k-distinguishable if there is an input S such that δ(X, S) and δ(Y, S) are (k-1)-distinguishable.
Step 3 − If Pk ≠ Pk-1, repeat Step 2, otherwise go to Step 4.
Step 4 − Combine kth equivalent sets and make them the new states of the reduced DFA.
Example
Let us consider the following DFA −

q

δ(q,0)

δ(q,1)

a

b

c

b

a

d

c

e

f

d

e

f

e

e

f

f

f

f

 Let us apply the above algorithm to the above DFA −

P0 = {(c,d,e), (a,b,f)}

P1 = {(c,d,e), (a,b),(f)}

P2 = {(c,d,e), (a,b),(f)}

Hence, P1 = P2.

There are three states in the reduced DFA. The reduced DFA is as follows −


Q

δ(q,0)

δ(q,1)

(a,b)

(a, b)

(c, d, e)

(c, d, e)

(c, d, e)

f

f

f

f

 


Answerd on:2017-06-27 Answerd By:Aparna-Dasgupta

Likes:
Be first to like this answer

Dislikes:
Be first to dislike this answer
Talk about this  Like  Dislike

You might like this video:Watch more here

Watch more videos from this user Here

Learn how to upload a video over here



Lets together make the web is a better place

We made eduladder by keeping the ideology of building a supermarket of all the educational material available under one roof. We are doing it with the help of individual contributors like you, interns and employees. So the resources you are looking for can be easily available and accessible also with the freedom of remix reuse and reshare our content under the terms of creative commons license with attribution required close.

You can also contribute to our vision of "Helping student to pass any exams" with these.
Answer a question: You can answer the questions not yet answered in eduladder.How to answer a question
Career: Work or do your internship with us.Work with us
Create a video: You can teach anything and everything each video should be less than five minutes should cover the idea less than five min.How to upload a video on eduladder