string pravartthanangal

computer shaasthrathil, aupachaarika bhasha sidhaanthathinte mekhalayil, pathivayi upayogikkunnathu vividha string functionukalaanu; ennirunnaalum, upayogikkunna notteshan computer prograaminginu upayogikkunnathil ninnu vyathyasthamaan, koodaathe saidhaanthika mekhalayil saadhaaranayaayi upayogikkunna chila functionukal prograaming cheyyumbol apoorvamaayi maathrame upayogikkaarulloo. eee lekhanam eee adisthaana padangalil chilath nirvachikkunnu.
charadukalum bhaashakalum.
aksharangalude oru parimithamaaya sreniyaanu string.
shoonyamaaya string formula _ 1 kondu soochippikkunnu.
rund string formulakalude samyojanam _ 2, formula _ 3 enniva formula _ 4 allengil formula _ 5 kondu kuravaanu.
shoonyamaaya stringumaayi samyojippikkunnath oru vyathyasavumilla formula _ 6.
stringukalude samyojanam associative aannu formula _ 7.
udaaharanathinu, formula _ 8.
oru bhasha ennathu parimithamo ananthamo aaya oru koottam stringukalaanu.
union, intersection muthalaaya saadhaarana settu pravarthanangalkku purame.bhashakalil samyojanam prayogikkaam
formula 9 umm formula 10 umm bhaashakalaanenkil, avayude konkattaneshan formula 11 formula 9 ll ninnulla eathenkilum stringinteyum formula 10 ll ninnulla eathenkilum stringinteyum konkattaneshan settaayi nirvachikkappedunnu, aupachaarika formula 14.
veendum, konkattaneshan dott formula _ 15 palappozhum hraswathaykkaayi ozhivaakkappedunnu.
shoonyamaaya string maathram ulkkollunna bhasha soothravaakyam _ 16 shoonyamaaya bhasha soothravaakyam _ 17 ll ninnu verthirichariyanam.
eathenkilum bhasha aadyathethumaayi samyojippikkunnath oru maattavum varuthilla soothravaakyam _ 18,
randaamathethumaayi samyojippikkumbol ellaayppozhum shoonyamaaya bhasha nalkunnu formula _ 19.
bhaashakalude samyojanam associative aannu formula _ 20.
udaaharanathinu, moonnu akka dasaamsha samkhyakalude koottamaaya formula _ 21 enna churukkezhuthu formula _ 22 aayi labikkum. ekapaksheeyamaaya neelamulla ellah dasaamsha samkhyakaludeyum koottam ananthamaaya bhaashayude oru udaaharanamaanu.
oru stringinte aksharamala.
oru stringinte aksharamala oru prathyeka stringle sambhavikkunna ellah pratheekangaludeyum koottamaanu. s" oru string aanenkil, athinte aksharamalaye soochippikkunnathu
oru bhasha soothravaakyathinte aksharamala _ 9 ennathu aupachaarikamaayi formula _ 9-nte eathenkilum stringle sambhavikkunna ellah pratheekangaludeyum koottamaanu
formula _ 26.
udaaharanathinu, string formula _ 28-nte aksharamaalayaan settu formula _ 27.
melpparanja formula _ 29 ennathu melpparanja bhasha formula _ 22-nteyum ellah dasaamsha samkhyakaludeyum bhaashayudeyum aksharamaalayaan.
string pakarakkaaran.
l" oru bhashayayirikkatte, σ athinte aksharamalayaayirikkatte. oru string substitution allengil lalithamaayi oru substitution ennathu σ-leeii pratheekangale bhaashakalilekku (orupakshe mattoru aksharamaalayilaayirikkam) mapp cheiyunna oru mapping "f" aanu. udaaharanathinu, oru aksharam "a" ωσ nalkiyaal, oraalkk "f" ("a") = "l" a "undu, avide" l "a" δ * ennathu δ aksharamalayulla chila bhaashayaan. eee mapping stringukalilekku ingane vyaapippikkam
shoonyamaaya stringinaayi ε, oppam
string "s" ω "l", aksharam "a" ωσ ennivaykku. string pakarakkar muzhuvan bhaashakalilekkum vyaapippikkam 
saadhaarana bhashakal string pakarakkaaran keezhil adanjirikkunnu. athaayath, oru saadhaarana bhaashayude aksharamalayile oro aksharavum mattoru saadhaarana bhasha upayogichu maattisthaapikkukayaanel, phalam ippozhum oru saadhaarana bhaashayaan.
athupole, sandarbha-rahita bhashakal string pakarakkaaran keezhil adaykkunnu.
oru lalithamaaya udaaharanam "f" uc (.) valiyaksharathilekku, athu iii ennu nirvachikkaam.jii. thaazhepparayunna reethiyil
f" uc-yude stringukalilekkulla vipuleekaranathinu, namukk e undu.jii.
bhaashakalilekkulla "eph" yusi yude vipuleekaranathinaayi, namukk iii undu.jii.
string homomorphism.
oro aksharathinum pakaram orotta string nalkunna oru string pakarakkaaranaan string homomorphism (aupachaarika bhasha sidhaanthathil palappozhum homomorphism ennu vilikkunnu). athaayath, formula _ 32, ivide formula _ 2 oru stringaanu, oro akshara formulakkum _ 34.
shoonyamaaya string string konkaattaneshante bainari pravartthanavum samrakshikkunna swatantra monoidile monoid morphisangalaanu string homomorphisangal. oru bhasha soothravaakyam _ 35 nalkiyaal, settu soothravaakyam _ 36 neey soothravaakyam _ 35 nte homomorphic imej ennu vilikkunnu. oru string soothravaakyam _ 2 nte vipareeta homomorphic imej ingane nirvachikkunnu
soothravaakyam _ 39
oru bhasha soothravaakyathinte vipareeta homomorphic chithram _ 35 aayi nirvachikkappedunnu
soothravaakyam _ 41
pothuve, formula _ 42, oraalkk undu
formula _ 43
oppam
formula _ 44
eathu bhasha soothravaakyathinum _ 35.
saadhaarana bhaashakalude klaas homomorphisangalkkum invezhs homomorphisangalkkum keezhil adanjirikkunnu. 
athupole, sandarbha-rahita bhashakal homomorphisangalkkum vipareeta homomorphisangalkkum keezhil adanjirikkunnu.
aksharamaalayude formula _ 47 leeii ellah "a" num formula _ 46 aanenkil oru string homomorphisathe ε-free (allengil iii-free) ennu parayunnu. lalithamaaya single-lettar substitution saifarukal (ε-free) string homomorphisangalude udaaharanangalaan.
melpparanja pakarakkaaran samanamaaya reethiyil nirvachichukondu oru udaaharana string homomorphism "jii" yusi nedaam "jii" yusi ("eiii") = "eiii",...g" uc (′0′) = ε, ennaal viramachinha aksharangalil "g" uc nirvachikkappedaathe anuvadikkunnu. 
vipareeta homomorphic chithrangalude udaaharanagal ivayaanu
randaamathe bhashayil, "g" uc ("g" uc −1 ({'a ",' bb")) = "g" uc ({'a "}) = {' a"} ≤ {'a ",' bb"}.
homomorphism "g" uc ennathu ε-free allah, kaaranam ithu e-yeei mapp cheiyunnu.jii. ′0′ muthal ε vare.
oro pratheekatheyum oru pratheekatthilekku mapp cheiyunna valare lalithamaaya string homomorphisathinte udaaharanam oru abysidic-encode cheytha string aassiyilekku parivartthanam cheyyuka ennathaanu.
string projection.
s" oru string formula _ 47 oru aksharamalayum aanenkil, formula _ 47-ll illaatha ellah pratheekangalum neekkam cheiyunnathiloode undaakunna stringaanu "s"-nte string projection. ithu formula _ 50 aayi ezhuthunnu. valathuvashath ninnu pratheekangal neekkam cheythukondu ithu aupachaarikamaayi nirvachikkappedunnu
ivide formula _ 1 shoonyamaaya stringine soochippikkunnu. oru stringinte projection adisthaanaparamaayi relational algibrayile oru projakshanu thulyamaanu.
string projection oru bhaashayude projakshanaayi prolsaahippikkaam. oru aupachaarika bhasha "l" nalkumbol, athinte projection nalkunnathu
valath, idathu bhagangal.
oru string "s" ll ninnulla "a" enna pratheekatthinte valath bhagam string "s" leeii valathuvashath ninnulla "a" enna pratheekatthinte vettimaattamaan. ithu formula _ 54 aayi soochippikkunnu. stringinu valathuvashath "a" illengil, phalam shoonyamaaya stringaanu. athinaal
shoonyamaaya stringinte bhagam edukkaam
athupole, oru monoid formula _ 58-nte oru upasett formula _ 57 nalkiyaal, oraalkk kwaasant upasettine ingane nirvachikkaam
oru stringinte idathuvashathu pravartthanangal nadakkunna idathu koshyantukal samaanamaayi nirvachikkaam.
hopcroftum ulman (1979) "l" 1, "l" 2 ennee bhaashakalude "l" 1/"l" 2 enna bhaagaphalathe athe aksharamaalaykk mukalil nirvachikkunnu.
ithu melpparanja nirvachanatthinte saamaanyavalkkaranamalla, kaaranam, oru string "kall", vyathyastha aksharangal "eiii", "bii" ennivaykku, hopcroftinteyum ulmaanteyum nirvachanam nalkunnathinekkaal elavu nalkunnathine soochippikkunnu.
oru singleton bhashayaaya "l" 1-nte idathu bhaagavum (hopcroft, ulman 1979-nuu samaanamaayi nirvachikkumbol) oru ekapaksheeyamaaya bhashayaaya "l" 2-neey brasosovsky derivative ennu vilikkunnu; "l" 2-neey oru saadhaarana padaprayogam prathinidheekarikkunnunde, idathu bhaagavum aakam.
vaakyaghadana bandham.
oru monoid formulayude 57 enna upasett formulayude sariyaaya bhagamaanu "s"-nte sariyaaya vaakyaghadana bandham ennu vilikkunna oru thulyatha bandhathe nirvachikkunnath. nalkia
kudumbatthinte sariyaaya kvoshyantukal parimithamaanengil maathram bandham vyakthamaayi parimitha soochikayude (parimithamaaya ennam thulyatha klaasukalundu) aanu; athaayath,
parimithamaanu. m" ennathu chila aksharamalayile vaakkukalude monoidaanengil, "s" oru saadhaarana bhaashayaan, athaayath, oru parimithamaaya avastha automaattan vazhi thirichariyaan kazhiyunna oru bhaashayaan. vaakyaghadana monoidukalekkurichulla lekhanathil ithu kooduthal vishadamaayi charcha cheythittundu.
sariyaaya radhaakkal.
oru string "kall" ll ninnu "a" enna aksharatthinte sariyaaya radhaakkal ennathu stringle "a" enna aksharatthinte aadya saannidhyam neekkam cheyyuka ennathaanu, valathuvashath ninnu aarambikkunnu. ithu formula _ 64 aayi soochippikkukayum aavarthichu nirvachikkukayum cheiyunnu
shoonyamaaya string ellaayppozhum raddaakkaavunnathaanu
vyakthamayum, sariyaaya radhakkal projection yathrayum
prefix.
oru stringinte prefixukal oru stringinte ellah prefixukaludeyum koottamaanu, oru bhashayumaayi bandhapetta
evide formula _ 69.
oru bhaashayude adaykkal enna prefix
udaaharanam 
soothravaakyam _ 71
soothravaakyam _ 72 aanenkil oru bhasha clossed prefix ennu vilikkunnu.
prefix closser oopparettar idempottant aannu
prefix relations oru bainari relations formulayanu, athaayath formula 76 aanenkil maathram formula 75. eee bandham oru prefix oordarinte oru prathyeka udaaharanamaanu.

