Reaalarvude kirjeldamine regulaarse avaldisega

Arvutis on märgijada tähendus määratud oma vormi, süntaksiga. Süntaks määratakse grammatikaga või lihtsamal juhul regulaarse avaldisega. Isegi lihtsatel struktuuridel vöib olla palju erijuhte - näiteks reaalarv vöib olla kujul 3.14, kuid vöib olla ka 0.3, 3.e-2 (=0.03) jne. Vaatame, kuidas tuleks arvutile kirjeldada järguga reaalarve, kui need on määratud järgnevate tingimustega (see on matemaatikas kasutatav kuju):
- ta peab sisaldama järgusümbolit e ja selle järel mingit täisarvu (märgiga või ilma); - kümnendosa eraldajaks on punkt . ja arvu ees märki pole - arv võib alata punktiga (täisosa puudub) ja punkt võib üldse puududa (arv algab järguga); kuid kui punkt on, peab kas enne punkti või selle järel olema vähemalt üks number (enne järku).

Neid süntaksinõdeid rahuldavad näiteks sellised reaalarvud: 3.17e+3p, 5.4e-7, .3e3, e-5 , kuid arvud .e+5 ja 3.14 ei rahulda, s.t. ei ole ülalesitatud reegltele vastavalt kirjutatud reaalarvud.

Reaalarvude kirjutamisel võib kasutada järgmisi sümboleid, s.t. reaalarvude terminalide tähestik on:

Mitteterminali Täisarv produktsioon kirjeldab vähemalt üht numbrit sisaldava täisarvu:

Regulaarse avaldise abil võib viimast produktsiooni kirjutada ka lühemalt: Täisarv

Number⁺ ja märkide vahemikke kasutades "otse", (abi)mitteterminali Number kasutamata:

Järgnevad produktsioonid kirjeldavad reaalarvu struktuuri; Algusosa kirjeldab reaalarvu numbrid kuni järgusümbolin, Lõpuosa kirjeldab järgu:

Algosa

Täisarv . Number^* e | e | . Täisarv e
Lõpposa

Märk Täisarv | Täisarv
Märk

+ | -
Reaalarv

Algosa Lõpposa

Asendades mitteterminalid Algusosa, Lõpuosa, Märk mitteterminali Reaalarv kirjeldavasse produktsiooni, saame reaalarve kirjeldava regulaarse avaldise:

Reaalarv

Algusosa Lõpuosa

((0..9)⁺ . (0..9)^* e | e | . (0..9)⁺ e ) ( [+ | -] (0..9)⁺ | (0..9)⁺ )

((0..9)⁺ . (0..9)^* e | e | . (0..9)⁺ e ) ( [+ | -] (0..9)⁺ )

Sellise süntaksiga märgijada tunnistab lõplik automaat (automaadi algolek on määratud sellesse "ei kusagilt" suunduva noolekesega, lõpolek - kahekordse ringikesega, Num tähistab vahemikku (0..9)):

1. Programmeerimiskeeles C on kahekordse täpsusega reaalarvu (double) süntaks veidi erinev älalkirjeldatust: eksponendimärk e ka puududa, kuid kui seda pole, peab arvus kindlasti olema punkt; eksponendimärgi kasutamisel peab selle ees kindlasti olema kas täis- või punktiga kirjutatud arv ja eksponendimärgi järel peab kindlasti olema täisarv (märgiga või ilma). Koosta regulaarne avaldis ja lõplik automaat C-keele double-arvude tunnistamiseks.

2. Programmeerimiskeeles LispMe kirjeldatakse reaalarvude süntaks järgmise grammatikaga:

real [sign] ureal
ureal mantiss [exponent] | alus digit+
sign '+' | '-'
mantiss digit+ ['.' digit*] | '.' digit+
exponent ('e' | 'E') ['+' | '-'] digit+
alus '#b' | '#B' | '#o' | '#O' | '#d' | '#D' | '#x' | '#X'

Koosta selle kirjelduse alusel Lisp-i reaalarve kirjeldav regulaarne avaldis ja neid tunnistav lõplik automaat.

3. Kompleksarvud kirjeldatakse Lisp-is järgmise grammatikaga (see kasutab eelmises ülesandes esitatud reaalarve kirjeldavaid produktsioone):

(viimane, märki '@' kasutav kuju on kompleksarvu esitus polaarkujul). Koosta Lisp-i kompleksarve kirjeldav regulaarne avaldis ja neid tunnistav lõplik automaat.

4. Programmeerimiskeeles Python on kompleksarvud näiteks 2+3j, 2.3-0J, 3-0.4j, s.t. reaal- ja kompleksosa on C-keele double-tüüpi, imaginaarühikut tähistab ja 'j' või 'J' ja imaginaarosa peab kindlasti olema ja imaginaarühik 'j' või 'J' peab otse järgnema imaginaarosale; kompleksarvu võib esitada ka funktsioonina complex(real, img), näiteks 1J * complex(0,1) = (-1+0j). Koosta Python-i kompleksarve kirjeldav regulaarne avaldis ja neid tunnistav lõplik automaat.