...Yazan : Şadi Evren ŞEKER
Özyineli diller matematik, mantık veya bilgisayar bilimlerinde geçen muntazam dillerden (formal language) birisidir. Genellikle kararverilebilir yani Turing makinesi (Turing machine) tarafından işlenebilir diller olarak kabul edilirler.
Özyineli diller Chomsky hiyerarşisinde yer almamaktadır.
Bir özyineli dili tanımlamak için iki önemli tanım yapılır. Birincisi dilin içerdiği alfabeden üretilebilen güç kümesinin (power set) özyineli alt kümesi (recursive subset) olmasıdır.
İkincisi ise Turing makinesi tarafından kabul edilebilir bir muntazam dil (formal language) olmasıdır. Yani Turing makinesi bu dili kabul edecek ve bu dil dışındaki durumlarda duracaktır (halting).
Bütün özyineli diller aynı zamanda özyineli sayılabilirdirler. Bütün CFG veya düzenli ifadeler özyineli dil olarak kabul edilebilir.
115 views