Automata Theory

[rahul_badboy]

Hello people!!I need ur help as i am unable to understand the an example regarding the smallest number of states in which a DFA can be constructed corresponding to an NFA for the same language!!.It is an example in the Automata theory book of hopcroft and ullman

Could someone explain it in a neat and simple way.

http://rapidshare.com/files/131114139/example_2.13.pdf.html

Thnks in advance!!

[CalmLogic]

Let me know if you still have questions after reading the following. The excerpt below explains why 2^n states are required to convert a NFA to DFA:

It is 2^n... this is because every state may have transitions to every other state .... so try creating graphs of all these different states... (in each case some could be isolated away from the start state).... what would then be the powerset for these states (basically all possible combinations) ?.. it has to be 2^n (either a state makes it to the graph or it dosent)

http://www.urch.com/forums/gre-compu...0-nfa-dfa.html (nfa to dfa)

As 2 can be defined as {0,1} (see natural number), 2^S (i.e., {0,1}^S) is the set of all functions from S to {0,1}

Power set - Wikipedia, the free encyclopedia

site:urch.com 2^n dfa nfa - Google Search

[rahul_badboy]

Thanks for reply CalmLogic ,i understood the example.

[yaprak]

hello,could you help me to solve this problem,please...ı must prove that {b^2i a^3j c^k : i,j,k integers and i>=j >k } is not regular languagethanks for your help...

[rahul_badboy]

@yaprak

it's pretty obvious buddy,u have to remember arbitrary number of b's till u have seen the a's which is not possible with a finite amount of memory available in dfa or nfa.

Take b^2i a^3j c^k of length n ,with given condition i>=j>k

divide it into three parts with the middle part a^3j ,so according to pumping lemma x y^b z for b>=0 should also be in the original language if xyz is regular.
b^2i (a^3j)^b c^k will disobey the rule at a point when 2i will be less than
3j.

Hope this is right and helps u

[p_hardev]

hi i have some doubt i question
if the order in which a fixed set of elements is inserted into a tree structure does not matter(the same tree results every time ) then the tree is

a) Heap 2) Binary search tree
c) AVL tree
d) Complete binary tree

which option is correct
according to me answer is (d)
i m sure are not
plz reply me

[yaprak]

thank you for your help...

[chandrayaan]

What exactly should i study for Automata Theory for GRE CS ?

Automata Theory is a vast field.