Deathline mekanı

#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

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)