Palindrom ifadeleri tanıyan deterministik olmayan PDA (NDPDA) tasarımı

Gönderen deathline tarihinde Friday, January 27. 2012 saat: 22:00

   Bu dili tanıyan PDA tasarlanıp, kod ile gerçeklenmesi.


 


 

Bu dilin grameri       


 


Bu dili tanıyan PDA 


 


PDA’nın çalışma ilkesi ; PDA’nın tanıdığı dizgiler, {0,1} alfabesindeki herhangi bir w  altdizgisi ile ile bunun tersinden oluşmaktadır. w ile wR arasında herhangi bir simge yer almayabileceği gibi, c simgesi yer alabilir.Bu dizgileri tanıyan PDA:

           


§  Önce w’nin simgelerini okur ve yığıta ekler, w’nin simgeleri okunurken PDA q0   durumundadır.


§  w  bitip , wR başladığında PDA q1  durumuna geçecektir.Ancak giriş dizgisinde w ’nin bitip wR nin başladığını belirten özel bir simge yoktur.Okunan simge w ’nin bir sonraki simgesi olabileceği gibi, w  ve wR arasındaki orta simge ya da wR nin ilk simgesi de olabilir.PDA deterministik olmayacaktır.


§  Silme durumunda (q1) geçen PDA wR nin simgelerini okur, ve okuduğu her simge için eğer yığıtın tepesinde aynı simge varsa bunu yığıttan çıkarır(siler).


§  Giriş dizgisinin tüm simgeleri okunduktan sonra , eğer yığıtın tepesinde Z0 varsa , PDA bunu da siler ve yığıt tamamen boşalır.


Yukarıdaki sözlü olarak tanımlanan işlemleri yapan PDA’nın hareket işlevi biçimsel aşağıdaki gibi tanımlanır.


 











 Read,Pop,Push


Şekil 1- PDA'nın JFlap Programı ile  grafiksel şeklinin oluşturulmuş hali


 


 


Biçimindeki ifadeler için kabul örneği


 


 









İfade Ağacı

 


 biçimindeki ifadeler için kabul örneği









İfade Ağacı

 


https://github.com/jasmarc/pushdown   adresinde bulduğum kod açıklamaları Türkçeleştirdim.


NDPDA ’ nın Ruby Programlama dili ile gerçeklenmiş hali;


 


Dosya adı : PDA.rb




#PDA’da bazı basit veri yapıları kullanılır.
#Bir konfigürasyon durum, okunmamış giriş verisi ve yığıttan oluşur
Configuration = Struct.new(:state, :input, :stack)
#Bir kural verilen tam bir konfigürasyon için bize nasıl hareket edebileceğimizi söyleyen, Move obje cinsinden bir koleksiyondur.
Rule = Struct.new(:number, :config, :moves)
#Bir Hareket durum değişikliklerinin ve yığıttaki değişikliklerin nasıl olacağını tanımlar.
Move = Struct.new(:rule_number, :state, :stack)

class PDA
def initialize(accepting_state, rules)
@accepting_state = accepting_state
@rules = rules.map! do |r|
Rule.new(r[0], Configuration.new(r[1], r[2], r[3]), r[4].map! { |m| Move.new(r[0], m[0], m[1]) })
end
@max = 0
#Bu hesaplama süresince başlangıç katarının uzunluğunu tutar.
end

def print_rules
@rules.each do |r|
print "#{r.number}:\t(#{r.config.state}, #{r.config.input}, #{r.config.stack}) -> "
r.moves.each { |m| print "(#{m.state}, #{m.stack})" }
print "\n"
end
end

def accept?(config)
@accept = false
computation_tree(config)
@accept
end

def count_leaf_nodes(config)
@leaf_nodes = 0
computation_tree(config)
@leaf_nodes
end
# Bu kısım PDA’nın gövdesi olup , hesaplama grafiği üzerindeki rekürsif şekilde dolaşmaktadır.
# Kabul veya hata durumunda sonlandırma
def computation_tree(config, verbose=false, whitespace="")
@max = @max > config.input.size ? @max : config.input.size
# Başlangıç giriş katarının uzunluğunu bilmemizi burası sağlıyor.
print "(#{config.state}, #{config.input}, #{config.stack})\n" if verbose

moves = get_moves(config)
# Mevcut konfigürasyona göre bazı hareket bilgilerini buradan alıyoruz.
# Terminal olaylarında ilk rekürziyonu kontrol etmemizi sağlıyor.
if config.state == @accepting_state && config.input.empty? && config.stack == "Z"
accept "Accept\n", verbose
elsif moves.nil? || moves.empty? || whitespace.size > 2 * @max
# Hiç hareket olmaması ve sonsuza giden hesaplamalarda hata olarak kabul edilmektedir.
crash "Crash! I couldn't find a rule for: state #{config.state}, input #{config.input}, stack #{config.stack}\n", verbose
else

moves.each do |m|
print "rule %2s #{whitespace}|-" % m.rule_number if verbose
rule = find_rule_by_number(m.rule_number)
if(!rule.nil? && rule.config.input.empty?)
unread = config.input
# Boşluk geçişi varsa girişi okumuyoruz.
else
unread = top(config.input)[1]
# Ancak yığıtın başındaki elemanı okuyoruz.
# Yeni konfigürasyonumuz , verilen harekete göre durum, okunmamış giriş ve yığıtın tepesindeki elemanın yerleştirilmesi.Ve tekrar rekürsiyonları.
end
computation_tree(Configuration.new(m.state, unread, m.stack + top(config.stack)[1]), verbose, whitespace + " ")
end
end
rescue NoMethodError => e
print "whitespace was [%s] and its length was [%d] and its class is %s\n" % [whitespace, whitespace.size, whitespace.class]
print "@max's class is %s\n" % [@max.class]
raise
end

private
# Bu metod verilen katarın ilk karakterini alır ve geriye iki dizi döndürür.
# Örneğin "Hello" would become ["H", "ello"]
# thus, top("Hello")[0] == "H" and top("Hello")[1] == "ello"
def top(str)
[str.slice(0, 1), str.size > 1 ? str.slice(1, str.size) : ""]
end


# Yukarıda verilen konfigürasyona göre, konfigürasyonla eşleşen bütün kuralları buluyoruz.
# Biz sadece kuralların tarif ettiği hareketleri istediğimiz için listeyi düzenliyoruz.
def get_moves(config)
rules = @rules.find_all do |r|
r.config.state == config.state \
&& (r.config.input == top(config.input)[0] || r.config.input.empty?) \
&& r.config.stack == top(config.stack)[0]
end
# Listeyi düzenliyoruz çünkü hareketleri istiyoruz , kuralları değil.
moves = rules.map { |r| r.moves }.flatten
end
# numarası verilen kuralı bulur.
def find_rule_by_number(number)
@rules.find { |r| r.number == number }
end



# Bu metod ekrana bir mesaj basar, yaprak noktalarını takip eder ve katarın kabul edilip edilmediğini kontrol eder.
def accept(msg, verbose)
print msg if verbose
@leaf_nodes += 1 unless @leaf_nodes.nil?
@accept = true
end
# Bu metod ekrana bir mesaj basar, yaprak noktalarını takip eder.
def crash(msg, verbose)
print msg if verbose
@leaf_nodes += 1 unless @leaf_nodes.nil?
end
end

Dosya Adı:  test.rb


require "test/unit"

require "PDA.rb"

class PDATests < Test::Unit::TestCase
  def setup
    @pal = PDA.new(:q2, [
             [1,  :q0, "a", "Z", [[:q0, "aZ"], [:q1, "Z"]]],
             [2,  :q0, "b", "Z", [[:q0, "bZ"], [:q1, "Z"]]],
             [3,  :q0, "a", "a", [[:q0, "aa"], [:q1, "a"]]],
             [4,  :q0, "b", "a", [[:q0, "ba"], [:q1, "a"]]],
             [5,  :q0, "a", "b", [[:q0, "ab"], [:q1, "b"]]], [...NEXT]
Sayfalar: PREVIOUS | 1 | 2 | NEXT | Tümünü
Twitter Bookmark Palindrom ifadeleri tanıyan deterministik olmayan PDA (NDPDA) tasarımı  at del.icio.us Facebook Google Bookmarks FriendFeed Digg Palindrom ifadeleri tanıyan deterministik olmayan PDA (NDPDA) tasarımı Mixx Palindrom ifadeleri tanıyan deterministik olmayan PDA (NDPDA) tasarımı Bloglines Palindrom ifadeleri tanıyan deterministik olmayan PDA (NDPDA) tasarımı Technorati Palindrom ifadeleri tanıyan deterministik olmayan PDA (NDPDA) tasarımı Fark this: Palindrom ifadeleri tanıyan deterministik olmayan PDA (NDPDA) tasarımı Bookmark Palindrom ifadeleri tanıyan deterministik olmayan PDA (NDPDA) tasarımı  at YahooMyWeb Bookmark Palindrom ifadeleri tanıyan deterministik olmayan PDA (NDPDA) tasarımı  at Furl.net Bookmark Palindrom ifadeleri tanıyan deterministik olmayan PDA (NDPDA) tasarımı  at reddit.com Bookmark Palindrom ifadeleri tanıyan deterministik olmayan PDA (NDPDA) tasarımı  at blinklist.com Bookmark Palindrom ifadeleri tanıyan deterministik olmayan PDA (NDPDA) tasarımı  at Spurl.net Bookmark Palindrom ifadeleri tanıyan deterministik olmayan PDA (NDPDA) tasarımı  at NewsVine Bookmark Palindrom ifadeleri tanıyan deterministik olmayan PDA (NDPDA) tasarımı  at Simpy.com Bookmark Palindrom ifadeleri tanıyan deterministik olmayan PDA (NDPDA) tasarımı  at blogmarks wong it! Bookmark using any bookmark manager! Stumble It! Print this article! E-mail this story to a friend! Identi.ca

Görüşler
Yorumları şöyle göster (Çizgisel | Ardarda işlem)

Görüş yok

Görüş ekle

Enclosing asterisks marks text as bold (*word*), underscore are made via _word_.
Standard emoticons like :-) and ;-) are converted to images.
E-Mail addresses will not be displayed and will only be used for E-Mail notifications.

To prevent automated Bots from commentspamming, please enter the string you see in the image below in the appropriate input box. Your comment will only be submitted if the strings match. Please ensure that your browser supports and accepts cookies, or your comment cannot be verified correctly.
CAPTCHA

 
 

Ajanda

Geri February '19
Mon Tue Wed Thu Fri Sat Sun
        1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28      

Hızlı Arama

Site Yönetim Arabirimi

Gerçekleştiren

Choose Language

Show tagged entries