22 Temmuz 2020 Çarşamba

Pumping Lemma

Giriş
Lemma farklı anlamlara gelebilir.

- Text Analysis konusunda baş kelime anlamına gelir.
- Programlama dili grameri konusunda ise önkabul, önsav anlamına gelir. 
- Ayrıca lemma kelimesi dil biliminde de kullanılıyor. Mesela şu soruda lemma kelimesi böyle sorulmuş. "Derivation of the Indo-European lemma *bʰréh₂tēr ‘brother’"

Stemmin and Lemmatization Nedir?
Açıklaması şöyle.
Stemming and Lemmatization
Stemming refers to the process of trimming words to bring them to their root form. For example, stemming algorithms reduce the terms argue, argued, argues, and arguing to the stem argue.

Lemmatization, on the other hand, determines the lemma of a word depending on its intended meaning. Unlike stemming, lemmatization uses a complex morphological analysis and dictionaries to select the correct lemma based on the context. For example, the lemmatization algorithm reduces the words argue, argued, argues, and arguing to argue.

Key Takeaway: Both stemming and lemmatization help train a system with data and clean the noise from the text. 
Pumping Lemma Nedir?
Pumping Lemma aslında bir Finite State Machine (FSM) 'dir.  Klasik bir FSM'den biraz farkılıdır. Klasik bir FSM şu koşulları sağlar.
1. State sayısı sınırlıdır
2. Geçiş yani transition sayısı sınırlıdır.
3. Başlangıç ve bitiş state'leri belirlidir.
Aynı şeyin daha detaylı maddelere bölünmüş açıklaması şöyle.
1.finite non-empty set of allowed states;
2.an initial state;
3.an alphabet ("allowed input symbols");
4.state-transition function;
5. and a set of final states.

Klasik bir FSM Neyi Sağlamaz
Klasik bir FSM  kaç tane girdi okuduğunu ve hangi state'lerden geçtiğini saklamaz.Pumping Lemma ise saklar. Aralarındaki fark budur.

Pumpin Lemman Ne İşe Yarar
Pumpin Lemma state sakladığı için başa dönüp tekrar aynı state'ten geçip geçmediğini anlayabilir.
Yani Pumping Lemma bir dilin regular olup olmadığını ispatlamak için kullanılır. Örneğin Regular Expression ile palindrome çözülemeyeceğini pumping lemma ile ispatlarız.

Pumping Lemman dilin Context Free olduğunu ispatlamaz.




Hiç yorum yok:

Yorum Gönder