Durum diyagramı - State diagram

Sadece açılıp kapatılabilen bir kapı için durum diyagramı

Bir devlet şeması türüdür şemada kullanılan bilgisayar bilimi sistemlerinin davranışlarını açıklamak için ve ilgili alanlarda. Durum diyagramları, açıklanan sistemin sınırlı sayıda durumdan oluşmasını gerektirir ; bazen bu gerçekten böyledir, diğer zamanlarda bu makul bir soyutlamadır . Biraz farklılık gösteren ve farklı anlamlara sahip birçok durum diyagramı biçimi mevcuttur .

Genel Bakış

Durum diyagramları, bir sistemin davranışının soyut bir tanımını vermek için kullanılır . Bu davranış, bir veya daha fazla olası durumda meydana gelebilecek bir dizi olay tarafından analiz edilir ve temsil edilir. Burada "her diyagram genellikle tek bir sınıfın nesnelerini temsil eder ve nesnelerinin farklı durumlarını sistem üzerinden izler".

Durum diyagramları, sonlu durum makinelerini (sonlu otomata da denir) grafik olarak temsil etmek için kullanılabilir . Bu, Claude Shannon ve Warren Weaver tarafından 1949 tarihli The Mathematical Theory of Communication adlı kitaplarında tanıtıldı . Diğer bir kaynak ise Taylor Booth , 1967 tarihli Ardışık Makineler ve Otomata Teorisi kitabında . Bir başka olası temsil, durum geçiş tablosudur .

Yönlendirilmiş grafik

Bir yönlendirilmiş grafik

Sonlu bir otomat (FA) için klasik bir durum diyagramı , aşağıdaki öğeleri (Q, Σ, Z, δ, q 0 , F) içeren yönlendirilmiş bir grafiktir :

  • Tepe Noktaları Q : normalde dairelerle temsil edilen ve benzersiz gösterge sembolleri veya içlerinde yazılı kelimelerle etiketlenen sonlu bir durum kümesi
  • Giriş sembolleri Σ : giriş sembollerinin veya işaretçilerinin sonlu bir koleksiyonu
  • Çıktı sembolleri Z : sonlu bir çıktı sembolleri veya belirleyiciler koleksiyonu

Çıkış fonksiyonu ω, matematiksel olarak ω  : Σ × Q → Z olarak gösterilen, giriş sembollerinin ve durumlarının sıralı çiftlerinin çıkış sembollerine eşlenmesini temsil eder .

  • Kenarlar δ : girdinin neden olduğu bir durumdan diğerine geçişleri temsil eder (kenarlara çizilen sembolleriyle tanımlanır). Mevcut durumdan bir sonraki duruma yönlendirilen bir ok olarak genellikle bir kenar çizilir. Bu eşleme, belirli bir sembolün girişinde meydana gelecek durum geçişini açıklar. Bu, matematiksel olarak yazılır ö  : Q, X Σ → Q FA tanımındaki δ (geçiş fonksiyonu), hem bu FA temsil eden bir diyagram bir kenarındaki bir kenar ile bağlı köşe çiftini ve sembol verilir, böylece . FA tanımındaki Item (q, a) = p maddesi, a giriş sembolü altındaki q adlı durumdan , bu makinede p durumuna geçişin meydana geldiği anlamına gelir. Bu FA'yı temsil eden diyagramda, bu, q ile etiketlenmiş tepe noktasından p ile etiketlenmiş tepe noktasına işaret eden bir işaret ile etiketlenmiş bir kenar ile temsil edilmektedir .
  • Başlangıç ​​durumu q 0 : (aşağıdaki örneklerde gösterilmemiştir). Başlangıç ​​durumu q 0 ∈ Q genellikle durumu işaret eden orijini olmayan bir okla temsil edilir. Daha eski metinlerde, başlangıç ​​durumu gösterilmez ve metinden çıkarılması gerekir.
  • Durumları kabul etme F : Örneğin otomatik verileri kabul etmek için kullanılırsa, F ∈ Q kabul etme durumudur . Genellikle çift daire şeklinde çizilir. Bazen kabul durum (lar) ı " F inal" (durma, yakalanmış) durumları olarak işlev görür .

Bir için deterministik sonlu otomat (DFA) nondeterministic FA (NFA), genelleştirilmiş nondeterministic FA (GNFA) veya Moore makinesi , giriş her kenarında gösterilir. Bir Mealy makinesi için , giriş ve çıkış her bir kenarda belirtilir ve bölü "/" ile ayrılır: "1/0", "0" sembolünün çıkmasına neden olan "1" sembolü ile karşılaşıldığında durum değişikliğini gösterir. Bir Moore makinesi için durum çıktısı genellikle durum çemberinin içine yazılır ve ayrıca durumun göstergesinden eğik çizgi "/" ile ayrılır. Bu iki gösterimi birleştiren varyantlar da vardır.

Örneğin, bir durumun birden fazla çıkışı varsa (ör. "A = saat yönünün tersine motor = 1, b = uyarı ışığı etkin değil = 0") diyagram bunu yansıtmalıdır: örneğin "q5 / 1,0", q5 durumunu a = 1, b = 0 çıktıları. Bu belirteç, eyaletin çemberinin içine yazılacaktır.

Örnek: DFA, NFA, GNFA veya Moore makinesi

S 1 ve S 2 durumları ve S 1 bir olduğunu kabul durumu veya bir son durum . Her kenar giriş ile etiketlenmiştir. Bu örnek, çift sayıda sıfır içeren ikili sayılar için bir alıcı gösterir.

DFAexample.svg

Örnek: Mealy makinesi

S 0 , S 1 ve S 2 durumlarıdır. Her kenar " j / k " ile etiketlenmiştir, burada j girdi ve k çıktıdır.

Basit bir Mealy makinesinin durum diyagramı

Harel statechart

Harel'in Statecharts'ın nesne yönelimli yöntemlere ve gösterime nasıl katkıda bulunduğunu gösteren şema

Bilgisayar bilimcisi David Harel tarafından icat edilen Harel statecharts, bir varyantın Birleşik Modelleme Dilinin (UML) bir parçası haline gelmesinden bu yana yaygın kullanım kazanıyor . Diyagram tipi , bir durumun parçası olarak süper durumların , ortogonal bölgelerin ve faaliyetlerin modellenmesine izin verir .

Klasik durum diyagramları, durumu tanımlayan her geçerli parametre kombinasyonu için farklı düğümlerin oluşturulmasını gerektirir. Bu, en basit sistemler ( durum ve geçiş patlaması ) dışında tümü için çok fazla sayıda düğüme ve düğümler arasında geçişlere yol açabilir . Bu karmaşıklık, durum diyagramının okunabilirliğini azaltır. Harel statecharts ile, statechart içinde çoklu fonksiyonlar arası durum diyagramlarını modellemek mümkündür. Bu çapraz işlevli durum makinelerinin her biri, durum tablosundaki diğer durum makinelerini etkilemeden dahili olarak geçiş yapabilir. Durum tablosundaki her bir işlevler arası durum makinesinin mevcut durumu, sistemin durumunu tanımlar. Harel statechart bir durum diyagramına eşdeğerdir, ancak ortaya çıkan diyagramın okunabilirliğini artırır.

Alternatif anlambilim

Durum diyagramlarını temsil etmek için kullanılabilen başka anlambilim kümeleri de vardır. Örneğin, gömülü kontrolörler için mantığı modellemek ve tasarlamak için araçlar vardır. Harel'in orijinal durum makineleri gibi bu diyagramlar, hiyerarşik olarak iç içe geçmiş durumları, ortogonal bölgeleri, durum eylemlerini ve geçiş eylemlerini destekler.

Durum diyagramları ve akış şemaları

Durum makinesi formalizme Yeni gelenler genellikle karıştırmayın durum diyagramları ile akış şemaları . Aşağıdaki şekil, bir durum şeması ile bir akış şemasının karşılaştırmasını göstermektedir . Bir durum makinesi (panel (a)), açık olaylara yanıt olarak eylemler gerçekleştirir. Aksine, akış şeması (panel (b)) açık olaylara ihtiyaç duymaz, bunun yerine faaliyetlerin tamamlanmasının ardından grafiğinde düğümden düğüme otomatik olarak geçiş yapar.

Durum diyagramı (a) ve akış şeması (b)

Akış şemalarının düğümleri, indüklenmiş durum grafiğindeki kenarlardır. Bunun nedeni, akış şemasındaki her düğümün bir program komutunu temsil etmesidir. Bir program komutu, yürütülecek bir eylemdir. Yani bu bir durum değildir, ancak programın durumuna uygulandığında başka bir duruma geçişle sonuçlanır.

Daha ayrıntılı olarak, kaynak kodu listesi bir program grafiğini temsil eder. Program grafiğini yürütmek (ayrıştırma ve yorumlama) bir durum grafiğiyle sonuçlanır. Yani her program grafiği bir durum grafiğini indükler. Program grafiğinin ilişkili durum grafiğine dönüştürülmesi, program grafiğinin "açılması" olarak adlandırılır.

Program grafiği bir dizi komuttur. Değişken yoksa, durum yalnızca program sayacından oluşur ve bu, yürütme sırasında programın neresinde olduğumuzu takip eder (uygulanacak bir sonraki komut nedir).

Bu durumda, bir komutu yürütmeden önce, program sayacı bir konumdadır (komut yürütülmeden önceki durum). Komutun yürütülmesi, program sayacını bir sonraki komuta taşır. Program sayacı tüm durum olduğundan, komutun yürütülmesi durumu değiştirdi. Dolayısıyla komutun kendisi iki durum arasındaki bir geçişe karşılık gelir.

Şimdi, değişkenler mevcut olduğunda ve yürütülen program komutlarından etkilendiğinde tam durumu düşünün. Daha sonra farklı program sayacı konumları arasında, yalnızca program sayacı değişmez, aynı zamanda yürütülen komutlar nedeniyle değişkenler de değerleri değiştirebilir. Sonuç olarak, bazı program komutlarını (örneğin bir döngüde) tekrar ziyaret etsek bile, bu programın aynı durumda olduğu anlamına gelmez.

Önceki durumda, program aynı durumda olacaktır, çünkü tüm durum sadece program sayacıdır, bu nedenle program aynı pozisyona denk geliyorsa (sonraki komut), aynı durumda olduğumuzu belirtmek yeterlidir. Bununla birlikte, durum değişkenler içeriyorsa, o zaman bunlar değeri değiştirirse, farklı değişken değerleri ile aynı program konumunda olabiliriz, yani programın durum uzayında farklı bir durumda olabiliriz. "Açılma" terimi, program grafiğinden durum grafiğini üretirken konumların bu çarpımından kaynaklanmaktadır.

Kendi kendine geçiş, başlangıç ​​ve son durumun aynı olduğu bir geçiştir.

Temsili bir örnek, bir sayacı taşana ve tekrar 0 olana kadar artıran bir do döngüsüdür. Do döngüsü aynı artış komutunu yinelemeli olarak yürütse de, program grafiği bir döngü yürütür, durum uzayında bir döngü değil, bir satırdır. Bu durum, program konumunun (burada döngü), kesin olarak artan (taşmaya kadar) sayaç değeriyle birleştirilmesinden kaynaklanır, bu nedenle, taşana kadar farklı durumlar sırayla ziyaret edilir. Taşma işleminden sonra sayaç tekrar 0 olur, böylece durum uzayında ilk durum tekrar ziyaret edilir ve durum uzayında bir döngü kapatılır (sayacın 0 olarak başlatıldığı varsayılarak).

Yukarıdaki şekil, durum diyagramlarının yaylarını akış şemasının işleme aşamalarıyla hizalayarak rollerin tersine döndüğünü göstermeye çalışır.

Akış şeması, bazı görevlerin baştan sona ilerlemesini açıkladığından (örneğin, kaynak kod girdisini bir derleyici tarafından nesne kodu çıktısına dönüştürmek) için bir akış şemasını üretimdeki bir montaj hattıyla karşılaştırabilirsiniz. Bir durum makinesinin genellikle böyle bir ilerleme nosyonu yoktur. Örneğin, bu makalenin üst kısmında gösterilen kapı durumu makinesi, "açık" duruma kıyasla "kapalı" durumda olduğunda daha gelişmiş bir aşamada değildir; basitçe açma / kapama olaylarına farklı tepki verir. Durum makinesindeki bir durum, bir işlem aşamasından ziyade belirli bir davranışı belirtmenin etkili bir yoludur.

Diğer uzantılar

İlginç bir uzantı, yayların herhangi bir sayıdaki durumdan herhangi bir sayıdaki duruma akmasına izin vermektir. Bu, yalnızca sistemin aynı anda birden fazla durumda olmasına izin verildiğinde anlamlıdır; bu, tek bir durumun yalnızca genel, küresel durumun yalnızca bir koşulunu veya başka bir kısmi yönünü tanımladığı anlamına gelir. Ortaya çıkan biçimcilik Petri ağı olarak bilinir .

Başka bir uzantı, akış şemalarının Harel istatistik grafikleriyle entegrasyonuna izin verir. Bu uzantı, hem olay güdümlü hem de iş akışı güdümlü yazılım geliştirmeyi destekler.

Ayrıca bakınız

Referanslar

Dış bağlantılar