Hvordan skille mellom DFA & NDFA

Deter og ikke-determinis Finite Automata er to typer konseptuelle "maskiner" designet for å sjekke om en gitt streng av symboler adlyder visse regler - hvis det er akseptabelt som en melding i noen språk eller kode. Den automata leser et enkelt symbol av gangen, og alltid finnes i en bestemt "tilstand". Hver stat en automater kan være i har et sett med regler for å reagere på det neste symbolet skal leses - det kan endre til en annen bestemt tilstand, eller forblir de samme. Dersom det etter en hel streng er lest, har automater inngått en av et sett av akseptable "endelige stater," strengen er grammatisk akseptabelt innenfor språket automater er testing for.

Bruksanvisning

1 Undersøk automater regler. Disse inkluderer: alle automater er mulige tilstander, sitt sett av endelige stater og effektene av alle mulige symbol på hver stat.

2 Sjekk for å se om noen av automater er stater har flere mulige reaksjoner på en bestemt symbol. Hvis noen gjør det, er det automater ikke-deterministisk - en NDFA. For eksempel, hvis en automater opprinnelige tilstand kan reagere på symbolet "A" enten ved å flytte til en annen stat eller ved å forbli den samme, er det en NDFA. En NDFA returnerer et positivt resultat hvis det er noen måte å nå en endelig tilstand ved hjelp av en gitt streng.

3 Husk at en DFA finnes for hver NDFA. Fordi en NDFA returnerer et positivt resultat for en bestemt streng må ha minst en vellykket bane gjennom det for at strengen, må det nødvendigvis være en tilsvarende DFA som vil akseptere at strengen, som bare inneholder reglene for enkelt bane som ble brukt. Her er et veldig enkelt eksempel: Tenk deg at du har en NDFA med en endelig tilstand kalt S1, som opprinnelig tilstand S0 reagerer på symbolet "A" enten ved å endre til S1 eller ved å forbli i S0. Denne maskinen vil godta en streng som består bare av "A", fordi det er en mulig vei å S1; og det er en tilsvarende DFA hvori "A" alltid endrer S1 til S0, dispensering med de ubrukte banen.