create non deterministic finite automaton
 

Hi there. I must create a NDFA which accepts the language ((0*|1)(1*0))*. The problem is i've done only few exercises about NDFA and i'm confused.
Does this language means that: 0*1*0 or 11*0 -> many times?

Do you know if this one is fine??
[img=http://img245.imageshack.us/img245/5189/helper2.th.jpg]

It's too difficult for me to find any resources and even a similar problem. Any help appreciated!

Re: create non deterministic finite automaton
 

Try a textbook on the theory of computation. They explain these quite clearly.

As for your first question, the answer is yes (from what I remember).

As for your second question, the answer is no, yours is not fine. In particular, the string 1 would pass your NFA, while it wouldn't pass the above language since every non-empty string in that language ends with 0.

Edit: Er, what was I thinking.

To make an NFA, note that essentially each node in the NFA corresponds to a point in between characters (the 0s and 1s) in the regular expression string. * corresponds to a lambda connection pointing back to the beginning of whatever it's starring (and at the beginning you have a choice of entering the subexpression or moving on) and | corresponds to a pair of lamba connections pointing to two different starting points.

Re: create non deterministic finite automaton
 

Hi,

I am Varun Gupta, a student at San jose State university and am working on finite automata.
I am totally new to the concept of finite automata.
Can anybody please provide me with a code in C or C++ or may b JAVA, that converts regular expression into finite automata?

That would be of a great help to me or if anyone can please give me a link for the same?

Thanks,
Varun

Re: create non deterministic finite automaton
 

i give u a DFA that accepts (a/b)*abb in 'C' .
i think this will helpfull to u.....(Varun Gupta.)

/*
To Check Whether Input String form DFA for (a/b)*abb */
#include<conio.h>
#include<stdio.h>
void main()
{
int i,state=1,n,len;
char a[21];
clrscr();
printf("Enter string to check DFA with Max 20 character \n");
scanf("%s",&a);
len=strlen(a);
if(len>20)
{
printf("Limit Exeeded");
getch();
exit(0);
}
a[len+1]=NULL;
for(i=0;i<len;i++)
{
if(a[i]>98 || a[i] <97)
{
printf("Not Valid");
getch();
exit(0);
}
}
i=0;
while(a[i]!=NULL)
{
if(a[i]=='a' && (state==1 || state==2 || state==3 || state==4))
state=2;
else if(a[i]=='b' && (state==1 || state==4))
state=1;
else if(a[i]=='b' && state==2)
state=3;
else if(a[i]=='b' && state==3)
state=4;
else if(a[i]==NULL && state==4)
state=4;
i=i+1;
}
if(state==4)
printf("Input string Form DFA for (a/b)*abb");
else
printf("Input string NOT Form DFA for (a/b)*abb");

getch();
}

Re: create non deterministic finite automaton
 

It shouldn't be too hard, there is an algorithm to do it in "Introduction to Computation" by Michael Sipser in chapter 1. It gives you a step-by-step process which seemed simple enough for me since you have the closure properties all the operators proven by construction.

For instance, the op's problem ((0*1*0)U(11*0))* can be tackled by taking into account the order of operations. We start by building NFA for empty string (sometimes called lambda or epsilon), then we build NFA for accepting single characters '0' and '1'.
Next, we use the proof of closure-property of * operator to build 0* and 1*.
Afterwards, we build two new NFA's

One, were we concatenate 0* with 1* with '0'. Using the epsilon-transitions are helpful in this matter.

The other NFA is done in a similar fashion, where we connect the NFA which accepts a single '1' with 1* using the epsilon-transition, then with the NFA which accepts a single '0' as well.

Then, using the closure-property of union, we unite 0*1*0 with 11*0. Again, epsilon-transitions make this much easier for us.

Finally, we add a new start state (as apart of the algorithm for making NFA's which mimicks * operator listed in the closure property of * operator) that only sends you to the last NFA but doesn't receive any incoming transitions from any other state.

Have the last states in both 0*1*0 and 11*0 connect with epsilon-transitions to the old start state of the prior NFA (where we united the two subproblems).

For someone like myself, I'd have an easier time reading something written in English how to make automata from regular expressions than by using code. I think most people are the same way, but for some programming is better.

Re: create non deterministic finite automaton
 

It shouldn't be too hard, there is an algorithm to do it in "Introduction to Computation" by Michael Sipser in chapter 1. It gives you a step-by-step process which seemed simple enough for me since you have the closure properties all the operators proven by construction.

For instance, the op's problem ((0*1*0)U(11*0))* can be tackled by taking into account the order of operations. We start by building NFA for empty string (sometimes called lambda or epsilon), then we build NFA for accepting single characters '0' and '1'.
Next, we use the proof of closure-property of * operator to build 0* and 1*.
Afterwards, we build two new NFA's

One, were we concatenate 0* with 1* with '0'. Using the epsilon-transitions are helpful in this matter.

The other NFA is done in a similar fashion, where we connect the NFA which accepts a single '1' with 1* using the epsilon-transition, then with the NFA which accepts a single '0' as well.

Then, using the closure-property of union, we unite 0*1*0 with 11*0. Again, epsilon-transitions make this much easier for us.

Finally, we add a new start state (as apart of the algorithm for making NFA's which mimicks * operator listed in the closure property of * operator) that only sends you to the last NFA but doesn't receive any incoming transitions from any other state.

Have the last states in both 0*1*0 and 11*0 connect with epsilon-transitions to the old start state of the prior NFA (where we united the two subproblems).

to OP: I would post the answer for you, but I don't have a means to do it nor the time. I think it's best for you to list an aim-account or ask for it to be sent over e-mail so I could send you a copy of that answer. However, probably - by now - you're already way past this so any help concerning this is unnecessary as you're likely working on Turin Machines now. --Good Luck

To Varun: For someone like myself, I'd have an easier time reading something written in English how to make automata from regular expressions than by using code. I think most people are the same way, but for some programming is better.