Skip to content

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

   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"]]],
             [6,  :q0, "b", "b", [[:q0, "bb"], [:q1, "b"]]],
             [7,  :q0, "", "Z", [[:q1, "Z"]]],
             [8,  :q0, "", "a", [[:q1, "a"]]],
             [9,  :q0, "", "b", [[:q1, "b"]]],
             [10, :q1, "a", "a", [[:q1, ""]]],
             [11, :q1, "b", "b", [[:q1, ""]]],
             [12, :q1, "", "Z", [[:q2, "Z"]]],
            ])

    @nonpal = PDA.new(:q2, [
             [1,  :q0, "a", "Z", [[:q0, "aZ"]]],
             [2,  :q0, "b", "Z", [[:q0, "bZ"]]],
             [3,  :q0, "a", "a", [[:q0, "aa"], [:q1, "a"]]],
             [4,  :q0, "b", "a", [[:q0, "ba"], [:q1, "a"]]],
             [5,  :q0, "a", "b", [[:q0, "ab"], [:q1, "b"]]],
             [6,  :q0, "b", "b", [[:q0, "bb"], [:q1, "b"]]],
             [7,  :q0, "", "Z", [[:q1, "Z"]]],
             [8,  :q0, "", "a", [[:q1, "a"]]],
             [9,  :q0, "", "b", [[:q1, "b"]]],
             [10, :q1, "a", "b", [[:q1, ""]]],
             [11, :q1, "b", "a", [[:q1, ""]]],
             [12, :q1, "", "Z", [[:q2, "Z"]]],
             [13, :q2, "a", "Z", [[:q2, "Z"]]],
             [14, :q2, "a", "Z", [[:q2, "Z"]]],
            ])

    @nonpal2 = PDA.new(:q1, [
             [1,  :q0, "", "Z",  [[:q1, "SZ"]]],
             [2,  :q1, "", "S",  [[:q1, "aAb"]]],
             [3,  :q1, "", "S",  [[:q1, "bAa"]]],
             [4,  :q1, "", "S",  [[:q1, "aSa"]]],
             [5,  :q1, "", "S",  [[:q1, "bSb"]]],
             [6,  :q1, "", "A",  [[:q1, ""]]],
             [7,  :q1, "", "A",  [[:q1, "Aa"]]],
             [8,  :q1, "", "A",  [[:q1, "Ab"]]],
             [9,  :q1, "a", "a", [[:q1, ""]]],
             [10, :q1, "b", "b", [[:q1, ""]]],
             [11, :q1, "", "Z",  [[:q2, "Z"]]],
            ])
  end

  def test_print_rules
    @pal.print_rules
  end
 
  def test_accept
    puts "testing acceptance for pal"
    ["a", "ab", "bb", "bbb", "", "bbaabb"].each do |s|
      puts "%-20s %s" % [s, @pal.accept?(Configuration.new(:q0, s, "Z"))]
    end
  end
 
  def test_count_leaf_nodes
    puts
    ["a", "ab", "bb", "aab", "aba", "bbb", "abba", "abbab", "abbaba", "bbbbbb"].each do |s|
      puts "%-20s %s" % [s, @pal.count_leaf_nodes(Configuration.new(:q0, s, "Z"))]
    end
  end
 
  def test_accept_for_non_pal
    puts "testing acceptance for non-pal"
    @nonpal2.print_rules
    @nonpal2.computation_tree(Configuration.new(:q0, "ab", "Z"), true)
    ["ab", "aab", "abab", "abbaba"].each do |s|
      assert(@nonpal2.accept?(Configuration.new(:q0, s, "Z")), s)
    end
    ["a", "bb", "aba", "bbb", "abba", "bbbbbb"].each do |s|
      assert(!@nonpal2.accept?(Configuration.new(:q0, s, "Z")), s)
    end
  end
end



 


 


Kaynaklar:





  •   Ünal Yarımağan , Özdevinirler Kuramı ve Biçimsel Diller, 2003.


  •  JFlap Programı ,(http://www.jflap.org)


  •  Grammer Editor,Carl Bruch (http://ozark.hendrix.edu/~burch/proj/grammar/)


  •  Jason Marcell ,https://github.com/jasmarc/pushdown





Yardımcı Kaynaklar:





  •   John C. Martin , Introduction To Languages And The Theory Of Computation 3rd. Ed.


  •  John.E.Hopcroft,.Jeffrey.D.Ullman ,Introduction to Automata Theory, Languages, and Computation 2nd. Ed. 2001


  •  Du Ding-Zhu, Ko Ker-I. Problem solving in automata, languages and complexity (Wiley, 2001)


  •  Introduction to the Theory of Computation - Sipser (MIT)



 


 


Trackbacks

No Trackbacks

Comments

Display comments as Linear | Threaded

No comments

Add Comment

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

Form options
Free Web Hosting