
nirdhaarak seemit swachaalit

ganana key siddhant mein, saiddhaantik computer vigyaan kii ack shakha, ack nirdhaarak parimit swachaalit (dee. aff. aeye.)-jise nirdhaarak parimit sweekaarak (dee. aff. aeye.), nirdhaarak seemit-avastha machine (dee. aff. aiss. aim.), yaa nirdhaarak seemit-avastha swachaalit (dee. aff. aiss. aeye.) key roop mein bhee jaanaa jaataa haye-ack seemit-avastha machine haye joe string dwara vishisht roop seey nirdhaarit ack avastha anukram key madhyam seey chalane vaale prateekon kii dee gaee string koo sweekaar yaa aswikar karati haye. "nirdhaarak" ganana daud kii vishishtata koo sandarbhit kartaa haye. seemit-avastha machines koo pakadane key liye sabse saral model kii khoj mein, vaaran mccullock aur walter pitt 1943 mein seemit automata key samaan ack avadharana pesh karane vaale pahale shodhkartaon mein seey they.
yeh aakriti ack raajya aarekh kaa upayog karke ack nirdhaarak seemit swachaalit koo darshaati haye. iss udaaharan automaton mein, teen avasthaaen hainh s0, s1, aur s2 (vritton dwara chitraatmak roop seey niroopit). swachaalit input key roop mein 0s aur 1s kaa ack seemit anukram letaa haye. pratyek raajya key liye, ack sankraman teer hotaa haye joe 0 aur 1 donon key liye ack agali sthiti kii or jaataa haye. ack prateek koo padhane parr, ack dee. aff. aeye. sankraman teer kaa paalan karke ack raajya seey dusare raajya mein "nirdhaarak roop seey" koodata haye. udaaharan key liye, yadi swachaalit vartamaan mein avastha s0 mein haye aur vartamaan input prateek 1 haye, tou yeh nirdhaarak roop seey avastha s1 parr koodata haye. ack dfa mein ack "praarambh sthiti" hoti haye (jahan seey kaheen seey aaney vaale teer dwara chitraatmak roop seey darshaaya jaataa haye) jahan ganana shuru hoti haye, aur "sweekaar avasthaon" kaa ack samooh (ack dohare vritt dwara chitraatmak roop seey darshaaya jaataa haye) joe ganana key safal honey parr paribhaashit karane mein madad kartaa haye.
dee. aff. aeye. koo ack amoort ganitiya avadharana key roop mein paribhaashit kiya gayaa haye, lekin aksar vibhinn vishisht samasyaon jaise kii shaabdik vishleshan aur pattern milan koo hull karane key liye hardware aur software mein lagu kiya jaataa haye. udaaharan key liye, ack dee. aff. aeye. software model curr sakata haye joe yeh taya kartaa haye kii email patey jaise online upayogkarta input vakyatmak roop seey maanya hain yaa naheen.
dee. aff. aeye. koo "gair-nirdhaarak seemit swachaalit (aine. aff. aeye.)" key liye saamaanyikrit kiya gayaa haye jisamen ack hii label key kaee teer hoe sakate hain joe ack raajya seey shuru hotey hain. powerset nirmaan vidhi kaa upayog karate hue, pratyek aine. aff. aeye. kaa anuvaad ack dee. aff. aeye. mein kiya jaa sakata haye joe ack hii bhasha koo pahachaantaa haye. dee. aff. aeye. aiss. aur aine. aff. aeye. aiss. bhee niyamit bhaashaon key samooh koo pahachaante hain.
aupchaarik paribhasha.
ack nirdhaarak seemit swachaalit ack 5-tupal haye, jisamen shamil hain
varnamala parr ack string honey dein. yadi avasthaon kaa ack crum nimnalikhit sthitiyon key saath maujood haye tou swachaalit string koo sweekaar kartaa haih
shabdon mein, pahali shart kahati haye kii machine praarambhik avastha mein shuru hoti haye. doosari shart kahati haye kii string key pratyek charitra koo dekhate hue, machine sankraman kaary key anusaar raajya seey raajya mein sankraman karegi. antim shart kahati haye kii machine sweekaar karati haye yadi antim input key kaaran machine sweekaar karane vaali sthitiyon mein seey ack mein rook jaati haye. anyatha, yeh kahaa jaataa haye kii swachaalit taar koo "aswikar" kartaa haye. joe string sweekaar kartaa haye vaha bhasha haye jise "maanyata praapt" haye aur iss bhasha koo "dwara darshaaya jaataa haye.
sweekaar avasthaon key binaa aur praarambhik avastha key binaa ack nirdhaarak seemit swachaalit koo sankraman pranali yaa ardh-swachaalit key roop mein jaanaa jaataa haye.
aupchaarik paribhasha key adhik vyaapak parichay key liye automata siddhant dekhein.
udaaharan key liye.
nimnalikhit udaaharan dwiaadhaari varnamala key saath ack dee. aff. aeye. kaa haye, jisake liye aavashyak haye kii input mein 0 kii summ sankhya hoe.
 kahaan
raajya kaa pratinidhitva kartaa haye kii abb taka input mein 0 kii ack summ sankhya rahee haye, jabaki ack visham sankhya koo darshaata haye. input mein a1 swachaalit kii sthiti koo naheen badalata haye. jaba input samaapt hoe jaayega, tou sthiti bataayegi kii input mein 0 kii summ sankhya haye yaa naheen. yadi input mein 0 kii summ sankhya hoti haye, tou yeh ack sweekaar karane vaali sthiti mein samaapt hoe jaayegi, isaliye input string sweekaar kii jaayegi.
dwara maanyata praapt bhasha niyamit abhivyakti cock _ 1 dwara dee gaee niyamit bhasha haye, jahan cock _ 2 clean starr haye, ee.jee., cocu _ 3 lagaatar kissy bhee sankhya (sambhavatah shoonya) koo darshaata haye.
vividhataaen.
poorna aur apoorna.
uparokt paribhasha key anusaar, nirdhaarak seemit swachaalit hamesha "poorna" hotey hainh way pratyek raajya seey pratyek input prateek key liye ack sankraman koo paribhaashit karate hain.
jabaki yeh sabse aam paribhasha haye, kuchh lekhak thodi alag dhaarana key liye nirdhaarak parimit swachaalit shabd kaa upayog karate hainh ack swachaalit joe pratyek sthiti aur pratyek input prateek key liye "adhikatam" ack sankraman koo paribhaashit kartaa haye; sankraman kaary koo aanshik honey kii anumati haye. jaba koee sankraman paribhaashit naheen hotaa haye, tou aisaa automaton rook jaataa haye.
sthaaniya automated.
ack sthaaniya swachaalit yantra ack dee. aff. aeye. haye, joe aavashyak roop seey poorna naheen haye, jisake liye ack hii label vaale sabhi kinaaron seey ack hii sheersh taka jaataa haye. sthaaniya swachaalit sthaaniya bhaashaon key varg koo sweekaar karate hain, jinake liye bhasha mein ack shabd kii sadasyata shabd parr dou lambai kii "sliding vindo" dwara nirdhaarit kii jaati haye.
ack varnamala "aeye" parr ack maihil graph ack nirdeshit graph haye jisamen sheersh samooh "aeye" aur sheershon key upasamuchchay "start" aur "finish" label kiye gaye hain. ack maihil graph dwara sweekaar kii gaee bhasha ack praarambh sheersh seey ack samaapti sheersh taka nirdeshit maargon kaa samooh haih iss prakaar graph ack swachaalit key roop mein kaary kartaa haye. maihil graph dwara sweekaar kii gaee bhaashaon kaa varg sthaaniya bhaashaon kaa varg haye.
yaadrichhikta.
jaba praarambhik avastha aur sweekaar avasthaon koo nazarandaj curr diyaa jaataa haye, tou avasthaon key ack dee. aff. aeye. aur aakar kii ack varnamala koo sheershon key ack degraph key roop mein dekhaa jaa sakata haye jisamen sabhi sheershon parr baahari-aark label (ack-baahari degraph) hotaa haye. yeh gyaat haye kii jaba ack nishchit purnank hotaa haye, uchch sambhavana key saath, tou yaadrichhik roop seey samaan roop seey chune gaye aise-out degraph mein sabse badaa dridhata seey judaa huaa ghatak (aiss. see. see.) raikhik aakar kaa hotaa haye aur ise sabhi sheershon dwara pahuncha jaa sakata haye. yeh bhee saabit hoe gayaa haye kii yadi vriddhi key roop mein badhane kii anumati dee jaati haye, tou poore degraph mein connectivity key liye erdos-renee model key samaan majboot connectivity key liye ack charan sankraman hotaa haye.
ack yaadrichhik dee. aff. aeye. mein, ack sheersh seey pahunchane yogya sheershon kii adhikatam sankhya uchch sambhavana key saath sabse badey aiss. see. see. mein sheershon kii sankhya key bahut karib hoti haye. yeh nyuntam inn-degree ack key sabse badey prerit upa-degraph key liye bhee sach haye, jise-core key nirdeshit sanskaran key roop mein dekhaa jaa sakata haye.
bund karane kii sampattiyan.
yadi dee. aff. aeye. una bhaashaon koo pahachaante hain joe dee. aff. aeye. pahchaanane yogya bhaashaon parr ack operation lagu karke praapt kii jaati hain tou dee. aff. aeye. koo operation key tahat bund kahaa jaataa haye. dee. aff. aeye. nimnalikhit sanchalanon key tahat bund hain.
pratyek operation key liye, raajya jatilata anusandhaan mein raajyon kii sankhya key sambandh mein ack ishtatam nirmaan nirdhaarit kiya gayaa haye.
choonki dee. aff. aeye. gair-nirdhaarak seemit swachaalit (aine. aff. aeye.) key barabar hain, isaliye inn bandon koo aine. aff. aeye. key bund karane key gunon kaa upayog karke bhee saabit kiya jaa sakata haye.
ack sankraman monoid key roop mein.
ack diye gaye dee. aff. aeye. key ack runn koo apane saath sankraman kaary key ack bahut hii samanya sutrikaran kii rachanaon key ack anukram key roop mein dekhaa jaa sakata haye. yahaan humm usa kaary kaa nirmaan karate hain.
diye gaye input prateek sootra 4 key liye, koee bhee sabhi sootra 7 key liye sootra 6 koo paribhaashit karke ack sankraman falan sootra 5 kaa nirmaan curr sakata haye. (iss chaal koo curring kahaa jaataa haye.) iss drishtikon seey, sootra _ 8 ack anya avastha praapt karane key liye q mein ack avastha parr "kaary" kartaa haye. phir koee bhee vibhinn karyon key sootra _ 8, sootra _ 10, aur isi tarah key karyon parr baar-baar lagu honey vaali falan sanrachana key parinam parr vichaar curr sakata haye. sootra _ 11 aksharon kii ack jodee koo dekhate hue, koee bhee ack nae falan sootra _ 12 koo paribhaashit curr sakata haye, jahan sootra _ 13 falan sanrachana koo darshaata haye.
spasht roop seey, iss prakriya koo punaraavarti roop seey jaari rakhaa jaa sakata haye, sootra _ 14 kii nimnalikhit punaraavarti paribhasha dete hueh
sootra _ 20 koo sabhi shabdon key liye paribhaashit kiya gayaa haye sootra _ 21. dee. aff. aeye. kaa ack runn sootra _ 20 kii rachanaon kaa ack anukram haye.
doharaae gaye kaary sanrachana ack monoid banaati haye. sankraman karyon key liye, iss monoid koo sankraman monoid, yaa kabhi-kabhi "parivartan ardhsamuh" key roop mein jaanaa jaataa haye. nirmaan koo bhee ulat diyaa jaa sakata haih ack sootra _ 20 diye jaane parr, koee ack sootra _ 24 kaa punarnirmaan curr sakata haye, aur isaliye donon vivaran samatulya hain.
laabh aur haani.
dee. aff. aeye. ganana key sabse vyaavhaarik model mein seey ack haye, kyonki input kii ack dhaara parr dee. aff. aeye. kaa anukaran karane key liye ack tuchchh raikhik samay, sthir-sthaan, online algorithm haye. isake alawa, ack dee. aff. aeye. pahchaanane key liye kushal algorithm hainh
kyonki dee. aff. aeye. koo "canonical roop" (nyuntam dee. aff. aeye.) mein cumm kiya jaa sakata haye, isaliye nirdhaarit karane key liye kushal algorithm bhee hainh
dee. aff. aeye. aiss. sanganakiya shakti mein gair-nirdhaarak seemit swachaalit (aine. aff. aeye. aiss.) key barabar hain. aisaa isaliye haye kyonki, sabse pahale koee bhee dee. aff. aeye. bhee ack aine. aff. aeye. haye, isaliye ack aine. aff. aeye. vahee curr sakata haye joe ack dee. aff. aeye. curr sakata haye. ack aine. aff. aeye. koo dekhate hue, powerset nirmaan kaa upayog karke ack dee. aff. aeye. kaa nirmaan kiya jaa sakata haye joe aine. aff. aeye. key roop mein ack hii bhasha koo pahachaantaa haye, halanki dee. aff. aeye. mein aine. aff. aeye. kii tulanaa mein badee sankhya mein sthitiyaan hoe sakati hain. haalaanki, bhale hii aine. aff. aeye. aiss. computational roop seey dee. aff. aeye. aiss. key barabar hain, uparokt samasyaon koo aine. aff. aeye. aiss. key liye bhee kushalata seey hull kiya jaanaa aavashyak naheen haye. aine. aff. aeye. aiss. key liye gair-saarvbhaumiktaa samasya pee. space poorna haye kyonki ghaatiya aakar mein sabse cumm aswikar karane vaale shabd key saath chhote aine. aff. aeye. hain. dee. aff. aeye. saarvbhaumik haye yadi aur kewal tabhi jaba sabhi raajya antim avasthaaen houn, lekin yeh aine. aff. aeye. aiss. key liye naheen haye. samaantaa, samavesh aur nyoonatamkaran kii samasyaaen bhee poorna hain kyonki unhein ack aine. aff. aeye. key poorak banaane kii aavashyakta hoti haye jisake parinamswarup aakar mein ghaatiya vriddhi hoti haye.
doosari or, seemit-avastha swachaalit bhaashaaen una bhaashaon mein sakhti seey seemit shakti kii hoti hain jinhen way pehchaan sakate hain; kaee saral bhaashaaen, jinamen koee bhee samasya shamil haye jise hull karane key liye nirantar sthaan seey adhik kii aavashyakta hoti haye, koo dee. aff. aeye. dwara pahachaana naheen jaa sakata haye. ack saral varnit bhasha kaa utkrisht udaaharan jise koee dee. aff. aeye. pehchaan naheen sakata haye, vaha haye koshthak yaa dike bhasha, i.ee.vaha bhasha jisamen shabd "() ())" jaise thheek seey jode gaye koshthak hotey hain. sahaj gyaan seey, koee bhee dee. aff. aeye. dike bhasha koo pehchaan naheen sakata haye kyonki dee. aff. aeye. ginati mein saksham naheen hainh ack dee. aff. aeye. jaise swachaalit yantra koo kissy bhee sambhaavit sankhya mein "vartamaan mein khule" koshthakon kaa pratinidhitva karane key liye ack raajya kii aavashyakta hoti haye, jiska arth haye kii ise aseemit sankhya mein raajyon kii aavashyakta hogi. ack aur saral udaaharan bhasha haye jisamen kuchh seemit lekin manmaane dhang seey "a" s kii sankhya key liye "anbn" roop key string shamil hain, jisake baad "b" s kii samaan sankhya haye.
label kiye gaye shabdon seey dee. aff. aeye. pehchaan.
sakaratmak" shabdon key ack samooh sootra _ 25 aur "nakaratmak" shabdon key ack samooh sootra _ 26 koo diye jaane parr koee bhee ack dee. aff. aeye. kaa nirmaan curr sakata haye joe sootra _ 27 seey sabhi shabdon koo sweekaar kartaa haye aur sootra _ 28 seey sabhi shabdon koo aswikar kartaa haih iss samasya koo "dee. aff. aeye. pehchaan" (sanshleshan, seekhana) kahaa jaataa haye.
jabaki "kuchh" dee. aff. aeye. kaa nirmaan raikhik samay mein kiya jaa sakata haye, nyuntam sankhya mein avasthaon key saath dee. aff. aeye. kii pehchaan karane kii samasya aine. pee.-poorna haye.
nyuntam dee. aff. aeye. pehchaan key liye pahala algorithm trachtenbroat aur barzdin dwara prastaavit kiya gayaa haye aur ise "tii. bee.-algorithm" kahaa jaataa haye.
haalaanki, tb-algorithm yeh maanata haye kii sootra _ 29 seey laker dee gaee lambai taka key sabhi shabd kissy bhee sootra _ 30 mein nihit hain.
baad mein, key. laing ney tii. bee.-algorithm key ack vistaar kaa prastaav rakhaa joe sootra _ 27 aur sootra _ 28, "traxbar" algorithm key baare mein kissy bhee dhaarana kaa upayog naheen kartaa haye.
haalaanki, traxbar nirmit dee. aff. aeye. kii nyoonatamata kii guaranti naheen detaa haye.
apane kaam mein ee.aim. gold ney nyuntam dee. aff. aeye. pehchaan key liye ack shodhaatmak algorithm kaa bhee prastaav rakhaa.
gold kaa algorithm maanata haye kii sootra _ 27 aur sootra _ 28 mein niyamit bhasha kaa ack "visheshta samooh" hotaa haye; anyatha, nirmit dee. aff. aeye. yaa tou sootra _ 27 yaa sootra _ 28 key saath asangat hoga.
anya ullekhaniya dee. aff. aeye. pehchaan algorithm mein aar. pee. aine. aaee. algorithm, blue-frinz sakshya-sanchaalit raajya-vilay algorithm shamil hain. 
aur khidki-adsum.
ack anya shodh disha vikaasvaadi algorithm kaa anuprayog haih smart state labeling vikaasvaadi algorithm koo ack sanshodhit dee. aff. aeye. pehchaan samasya koo hull karane kii anumati dee gaee haye jisamen prashikshan detta (sootra _ 27 aur sootra _ 28 sett kartaa haye) iss arth mein "shore" haye kii kuchh shabdon koo galat vargon key liye jimmedaar thaharaaya jaataa haye.
ack aur kadam aage badhana margine jey dwara satver key anuprayog key kaaran haye. aich. heul aur aiss. vaastavah booliyan sootra kii santoshjanakta taya karane key liye nyuntam dee. aff. aeye. pehchaan samasya cumm hoe jaati haye. mukhya vichaar input seton key aadhar parr ack samvardhit upsarg-vriksh sweekaarak (sambandhit label key saath sabhi input shabdon vaalaa ack trie) kaa nirmaan karna haye aur sootra 39 raajyon key saath ack dee. aff. aeye. khojane kii samasya koo cumm karke sootra 39 raajyon key saath vriksh key sheershon koo "rung" karane kii samasya koo iss tarah seey cumm karna haye kii jaba ack rung key saath sheersh ack sthiti mein vilay hoe jaate hain, tou utpann swachaalit nirdhaarak hotaa haye aur sootra 27 aur sootra 28 kaa anupaalan kartaa haye.
haalaanki yeh drishtikon nyuntam dee. aff. aeye. khojane kii anumati detaa haye, lekin jaba input detta kaa aakar badhata haye tou yeh nishpaadan samay key ghaatiya visfot seey peedit hotaa haye.
isaliye, heul aur verver key praarambhik algorithm koo baad mein sait solver nishpaadan seey pahale adsum algorithm key kaee charanon koo banaane key saath badhaaya gayaa haih defassat algorithm.
yeh samasya kii khoj sthaan koo cumm karane kii anumati detaa haye, lekin nyuntam guaranti key nuksan kii or leey jaataa haye.
khoj sthaan koo cumm karane kaa ack aur tarika uliyantsev aur anya dwara prastaavit kiya gayaa haye. breadth-first search algorithm key aadhar parr naee samroopata todane key madhyam seh
praarambhik avastha seey shuru kiye gaye bee. aff. aiss. algorithm key anusaar vaanchhit dee. aff. aeye. kii avasthaon koo kramaankit karane key liye vivash kiya jaataa haye. yeh drishtikon isomorphic automata koo samaapt karke sootra _ 43 dwara khoj sthaan koo cumm curr detaa haye.
samkaksh model.
kewal padhane yogya sahee-chalane vaali turing masheenen.
kewal padhane yogya sahee-chalane vaali turing masheenen ack vishesh prakaar kii turing machine hain joe kewal sahee chalati hain; yeye
lagbhag dee. aff. aeye. key barabar hain.
ekal anant tape parr adharit paribhasha 7-tupple haye.
kahaan
machine hamesha ack niyamit bhasha sweekaar karati haye. bhasha key khaali naa honey key liye sett kaa cumm seey cumm ack tatva (ack thaharaav sthiti) honah chaahiye.

