Theorie van automaten is een theoretische tak van informatica en wiskunde. Het is de studie van abstracte machines en de rekenproblemen die met behulp van deze machines kunnen worden opgelost. De abstracte machine wordt de automaat genoemd. De belangrijkste motivatie achter het ontwikkelen van de automatentheorie was het ontwikkelen van methoden om het dynamische gedrag van discrete systemen te beschrijven en analyseren.
Deze automaat bestaat uit toestanden en overgangen. De Staat wordt vertegenwoordigd door cirkels , en de Overgangen wordt vertegenwoordigd door pijlen .
Automaten zijn het soort machines dat een bepaalde reeks als invoer gebruikt en deze invoer doorloopt een eindig aantal toestanden en kan in de eindtoestand terechtkomen.
Er zijn de basisterminologieën die belangrijk zijn en vaak worden gebruikt in automaten:
Symbolen:
Symbolen zijn een entiteit of individuele objecten, die elke letter, alfabet of elke afbeelding kunnen zijn.
Voorbeeld:
1, a, b, #
Alfabetten:
Alfabetten zijn een eindige reeks symbolen. Het wordt aangegeven met ∑.
Voorbeelden:
∑ = {a, b} ∑ = {A, B, C, D} ∑ = {0, 1, 2} ∑ = {0, 1, ....., 5] ∑ = {#, β, Δ} Snaar:
Het is een eindige verzameling symbolen uit het alfabet. De string wordt aangegeven met w.
Voorbeeld 1:
Als ∑ = {a, b}, zijn verschillende strings die uit ∑ kunnen worden gegenereerd {ab, aa, aaa, bb, bbb, ba, aba.....}.
- Een string waarin geen symbolen voorkomen, wordt een lege string genoemd. Het wordt weergegeven door ε.
- Het aantal symbolen in een string w wordt de lengte van een string genoemd. Het wordt aangegeven met |w|.
Voorbeeld 2:
w = 010 Number of Sting |w| = 3
Taal:
Een taal is een verzameling geschikte tekenreeksen. Een taal die over Σ wordt gevormd, kan dat wel zijn Eindig of Oneindig .
Voorbeeld 1
L1 = {Set of string of length 2} = {aa, bb, ba, bb} <strong>Finite Language</strong> Voorbeeld: 2
L2 = {Set of all strings starts with 'a'} = {a, aa, aaa, abb, abbb, ababb} <strong>Infinite Language</strong>