how do i solve?good-bad NFA!!

[shomashoma]

this is a problem iv nt been able to solve..tried still not getting an answer
Imagine that an NFA is divided into good and bad states represented by G and B resp..also G and B are mutually exclusive..now a string is accpted by the new NFA only if all computations on w(string) end either in the neutral state or the good state but not in the bad state..we have to proove that the language accpted by this are regular languages.
plz help solving me this..help appreciated

[Duoas]

I'm not sure I understand your homework assignment.

You have three halt states: G (good), neutral, and B (bad).

However, your NFA only accepts for G and neutral. Hence, you really only have two halt states: G (good) and neutral.

This is all the information you have given me. With what you know (that I might not) about your NFA, can you prove that it is a regular language?

Hint: what is the definition/properties of a regular language, and what is the definition/properties of an NFA? (Or DFA, if you have already seen proof that a DFA and an NFA are equivalent).

[shomashoma]

I will restate the whole problem..the one that was given to me..
Suppose we alter the defination of an NFA so that we now identify 2 types of states in its state set Q:the good states G which is a subset of Q and the Bad states B which is a subset of Q,where G and B are mutually exclusive.We also alter the defination of acceptace:the automaton now accepts input w if,considering all possible computations on w,some computation ends in G and no computation ends in B.Call this new type of NFA a GOOD-BAD-NFA.
Proove that th class of languages recognized by GOOD-BAD-NFAs is the class of regular languages.

[Duoas]

OK, so there are no neutral states.

I'm afraid I can't give you much more help than I already have, since this homework is a test of definitions.

Hint: if the modified NFA cannot halt on B, then what difference does it make if B is part of the automaton?

[sarehu]

shomashoma, remember that two sets S and T are equal if S is a subset of T and T is a subset of S. You know that the set of regular languages are those accepted by DFAs and NFAs. Hint hint.

[shomashoma]

What if all the halting states that existed before the automata was modified are now the bad states..den how would any language be accepted???

[shomashoma]

see the thing is that it is mentioned that all possible computations on the string should end in good states only..If for example a state on application of say 0 goes on a good state as well as a bad state..den that string is not accpeted..this is mentioned in the question written above..So what wud happn if say the language for the original NFA os say 0*1..and all the 1 point to atleast 1 bad state..nd ya we could convert the NFA to the DFA but the DFA would fail in the above mentioned scenario..!!so what do v do??

[sarehu]

There is no converting, just reasoning related to sets.

[Duoas]

I could go to Ireland and speak to someone in Spanish, but I would get deported. (Just because someone who speaks Spanish can go and speak it in Ireland does not mean that he will be accepted by the Irish people.)

We are really at our limits for explaining things more clearly for you without just giving the answer away (I would argue that we already did...)

Think about it a little...

[EDIT] By the way, I'm not being rude. Everything in this post applies directly to your problem.

[rajmitul]

/*NFA --> DFA conversion program
*/
#include <stdio.h>
#include <string.h>
#include<conio.h>
#define STATES 25
#define SYMBOLS 20

int N_symbols; /* number of input symbols */
int NFA_states; /* number of NFA states */
char *NFAtab[STATES][SYMBOLS];

int DFA_states; /* number of DFA states */
int DFAtab[STATES][SYMBOLS];

/*
Print state-transition table.
State names: 'A', 'B', 'C', ...
*/
void put_dfa_table(
int tab[][SYMBOLS], /* DFA table */
int nstates, /* number of states */
int nsymbols) /* number of input symbols */
{
int i, j;

puts("STATE TRANSITION TABLE");

/* input symbols: '0', '1', ... */
printf(" | ");
for (i = 0; i < nsymbols; i++) printf(" %c ", '0'+i);

printf("\n-----+--");
for (i = 0; i < nsymbols; i++) printf("-----");
printf("\n");

for (i = 0; i < nstates; i++) {
printf(" %c | ", 'A'+i); /* state */
for (j = 0; j < nsymbols; j++)
printf(" %c ", 'A'+tab[j]);
printf("\n");
}
}

/*
Initialize NFA table.
*/
void init_NFA_table()
{
/*
NFA table for ex.21 at p.76

NFAtab[0][0] = "01";
NFAtab[0][1] = "0";
NFAtab[1][0] = "";
NFAtab[1][1] = "01";

NFA_states = 2;
DFA_states = 0;
N_symbols = 2;
*/
/*
NFA table for ex.17 at p.72
*/
NFAtab[0][0] = "12";
NFAtab[0][1] = "13";
NFAtab[1][0] = "12";
NFAtab[1][1] = "13";
NFAtab[2][0] = "4";
NFAtab[2][1] = "";
NFAtab[3][0] = "";
NFAtab[3][1] = "4";
NFAtab[4][0] = "4";
NFAtab[4][1] = "4";

NFA_states = 5;
DFA_states = 0;
N_symbols = 2;
}

/*
String 't' is merged into 's' in an alphabetical order.
*/
void string_merge(char *s, char *t)
{
char temp[STATES], *r=temp, *p=s;

while (*p && *t) {
if (*p == *t) {
*r++ = *p++; t++;
} else if (*p < *t) {
*r++ = *p++;
} else
*r++ = *t++;
}
*r = '\0';

if (*p) strcat(r, p);
else if (*t) strcat(r, t);

strcpy(s, temp);
}

void get_next_state(char *nextstates, char *cur_states,
char *nfa[STATES][SYMBOLS], int n_nfa, int symbol)
{
int i;
char temp[STATES];

temp[0] = '\0';
for (i = 0; i < strlen(cur_states); i++)
string_merge(temp, nfa[cur_states-'0'][symbol]);
strcpy(nextstates, temp);
}

int state_index(char *state, char statename[][STATES], int *pn)
{
int i;

if (!*state) return -1; /* no next state */

for (i = 0; i < *pn; i++)
if (!strcmp(state, statename)) return i;

strcpy(statename, state); /* new state-name */
return (*pn)++;
}

int nfa_to_dfa(char *nfa[STATES][SYMBOLS], int n_nfa,
int n_sym, int dfa[][SYMBOLS])
{
char statename[STATES][STATES];
int i = 0; /* current index of DFA */
int n = 1; /* number of DFA states */

char nextstate[STATES];
int j;

strcpy(statename[0], "0"); /* start state */

for (i = 0; i < n; i++) { /* for each DFA state */
for (j = 0; j < n_sym; j++) { /* for each input symbol */
get_next_state(nextstate, statename, nfa, n_nfa, j);
dfa[j] = state_index(nextstate, statename, &n);
}
}

return n; /* number of DFA states */
}

void main()
{
clrscr();
init_NFA_table();
DFA_states = nfa_to_dfa(NFAtab, NFA_states, N_symbols, DFAtab);
put_dfa_table(DFAtab, DFA_states, N_symbols);
getch();
}