Language Technology:regular-set

From Tieteen termipankki
Revision as of 10:50, 8 November 2015 by Viggo Kann (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

regular language

regular language(suositeltu)
regular set(vältettävä)
Definition yksinkertaisilla operaatioilla yhden merkin mittaisista tai tyhjistä merkkijonoista muodostettavissa oleva merkkijonojen joukko
Explanation Tietyn aakkoston S merkeistä koostuvien merkkijonojen joukko on säännöllinen kieli, jos se voidaan muodostaa (1) tyhjästä joukosta (joka on säännöllinen kieli), (2) tyhjästä merkkijonosta (joka on säännöllinen kieli), (3) aakkoston S mistä tahansa merkistä muodostetusta yhden merkin mittaisen merkkijonon muodostamasta joukosta (jollaiset ovat säännöllisiä kieliä), seuraavassa luetuilla operaatioilla. Kahdesta säännöllisestä kielestä P ja Q voidaan muodostamaa niiden yhdiste (unioni) P ∪ Q, tai ne voidaan asetellla peräkkäin PQ tai säännöllistä kieltä P voidaan toistaa P* ja näin saadut joukot ovat myös säännöllisiä kieliä. Vain tällä tavalla muodostettavissa olevat joukot ovat säännöllisiä kieliä.

Esim. joukko {"", "aa", "aaaa", ...} joka koostuu merkkijonoista, joissa on parillinen määrä a-kirjaimia on säännöllinen kieli. Sen voi katsoa muodostuneen kahdesta joukosta {"a"} peräkkäinasettelulla, jolloin saadaan joukko {"aa"} ja sen jälkeen toistamalla tätä (nolla, yhden tai useamman kerran), jolla saadaan haluttu joukko.

Jokaiselle säännölliselle kielelle on olemassa äärellinen automaatti, joka hyväksyy täsmälleen kyseisen kielen merkkijonot ja kääntäen, jokaisen äärellisen automaatin hyväksymät merkkijonot muodostavat säännöllisen kielen. Samoin, ns. säännölliset kieliopit tuottavat vain säännöllisiä kieliä ja kaikki säännölliset kielet voidaan kuvata sopivilla säännöllisillä kieliopeilla. Säännöllisillä lausekkeilla voidaan määritellä säännöllisiä kieliä.

Equivalents

langage rationnelranska
reguljär mängd (luo nimityssivu)ruotsi
reguljärt språk (luo nimityssivu)ruotsi
reguläre Sprachesaksa
säännöllinen kielisuomi
säännöllinen joukkosuomi

Related Concepts



References

Lähdeviittaus tähän sivuun:
Tieteen termipankki 19.11.2019: Language Technology:regular-set. (Tarkka osoite: https://tieteentermipankki.fi/wiki/Language Technology:regular-set.)


Siirry tarkastelemaan sivun muokkaushistoriaa →