Struktur Diskrit : Finite-State Machine dengan Tanpa Output
Language Recognition
One of the most important applications of finite-state machines is in language recognition. The application plays a fundamental role in the design and construction of compilers for programming languages. There are other types of finite-state machines that are specially designed for recognizing languages. Instead of producing output, these machines have final states.
A string is recognized if and only if it takes the starting state to one of these final states
Set of Strings
Suppose that A and B are subsets of V*, where V is a vocabulary. The concatenation of A and B, denoted by AB, is the set of all strings of the form xy, where x is a string in A and y is a string in B.
Example: let A={0, 11} and B= {1, 10, 110}. Find AB and BA
Answer:
AB = {01,010,0110,111,1110,11110}
BA = {10, 111, 100, 1011, 1100, 11011}
From the definition of the concatenation of two sets of strings, we can define A^n, for n=0,1,2,…
A^0 = {λ}
A^(n+1) = A^n A, for n=0,1,2,…
Example: Let 𝐴={1,00}. Find 𝐴𝑛, for 𝑛=0,1,2, and 3.
Solution:
- 𝐴0 = {𝜆}
- 𝐴1 = 𝐴0𝐴={𝜆}𝐴={1, 00}.
- 𝐴2 = {11,100,001,0000}
- 𝐴3 = {111,1100,1001,10000,0011,00100,00001,000000}
Kleene Closure
What are the Kleene closures of the sets 𝐴={0}, 𝐵={0,1}, and 𝐶={11}
- 𝐴∗ = {0 n | 𝑛=0, 1, 2,…}
- The Kleene closure of 𝐵 is the concatenation of an arbitrary number of strings, where each string is either 0 or 1
- 𝐶∗ = {12n | 𝑛=0, 1, 2, …}
Finite State Automata (FSA)
Determine The Languages
Determine the languages recognized by the finite-state automata M_1:
Answer: L(M_1 )={1^n ┤|n=0, 1, 2,…}
Determine the languages recognized by the finite-state automata M_2 and M_3:
Answer: L(M_2 ) = {1, 01}
Answer: L(M_3 ) = {0^n,0^n 10x ┤|n=0, 1, 2, …, x is any string}
Designing FSA
Equivalent FSA
Two finite-state automata are equivalent if they recognize the same language.
Nondeterministic FSA
There is another important type of finite-state automaton in which there may be several possible next states for each pair of input value and state Called nondeterministic FSA.
Nondeterministic FSA are important in determining which languages can be recognized by a FSA.
The languange recognized by this machine is: {0n,0n01,0n11|n ³ 0}.
Theorem
Example:
Sumber
Slide Strukdis : FSM Tanpa Output
Posting Komentar