Formalni jezik
U matematici, logici i računarstvu, formalni jezik L {\displaystyle {\boldsymbol {L}}} se sastoji od skupa konačnih nizova elemenata konačnog skupa A {\displaystyle {\boldsymbol {A}}} znakova (simbola). Matematički, to je neuređen par L = { A , F } . {\displaystyle {\boldsymbol {L}}=\{{\boldsymbol {A}},{\boldsymbol {F}}\}.} Među najuobičajenijim primjenama, formalni jezik može biti shvaćen kao: kolekcija riječi ili kolekcija rečenica U prvom slučaju, skup A {\displaystyle {\boldsymbol {A}}} se zove abeceda jezika L {\displaystyle {\boldsymbol {L}}} , a elementi skupa F {\displaystyle {\boldsymbol {F}}} se zovu riječi. U drugom slučaju, skup A {\displaystyle {\boldsymbol {A}}} se zove leksikon ili vokabular skupa F {\displaystyle {\boldsymbol {F}}} , dok se elementi skupa F {\displaystyle {\boldsymbol {F}}} zovu rečenice. Matematička teorija koja se općenito bavi proučavanjem formalnih jezika se zove teorija formalnih jezika. Kao primjer formalnog jezika, abeceda može biti { a , b } {\displaystyle \left\{a,b\right\}} , a riječ (string, niz znakova) nad tim alfabetom može biti a b a b b a {\displaystyle ababba\,} . Tipični jezik nad abecedom, koji sadrži tu riječ, bi bio skup svih riječi koje sadrže isti broj znakova a {\displaystyle a\,} and b {\displaystyle b\,} . Prazan niz (ili prazna riječ) je riječ dužine 0, i često se označava znakom e {\displaystyle e\,} , ϵ {\displaystyle \epsilon \,} ili Λ {\displaystyle \Lambda \,} . Iako je abeceda konačan skup i svaka riječ je konačne dužine, jezik može imati beskonačno mnogo riječi (jer dužina riječi koje sadrži ne mora nužno imati gornju granicu). Često postavljano pitanje o formalnim jezicima jest "koliko je teško odlučiti da li zadana riječ pripada nekom određenom jeziku?" Ovo je područje proučavanja teorije računanja i teorije složenosti.