Limbaje Formale si Automate

Incarcat la data: 26 Februarie 2010

Autor: Alexandra Lavinia

Pret: 80 credite

Numar pagini: 47

Tip fisier: zip

Marime fisier: 714 kb

This DFA (reject state, transitions not shown) has two sections, corresponding to two types of currency strings: dollars and cents. The states q1-q3 represent the cents, and q4-q9 represent the dollars. The cents representation of currency is a one or two-digit number followed by "c". The number is either a positive one-digit number (which takes the machine to q2), 0 (which takes the machine to q1), or a positive two-digit number where the first digit is not 0 (which takes the machine to q1 through q2). Note that the last two cases can lead to the same state since both are only valid if followed immediately by "c". This machine accepts a string at q3 after a single "c" following this number.

The dollar representation of currency is either (1) a whole amount of dollars (e.g. $5, $221), or (2)
dollars plus change (e.g. $3.21, $19.95). Both of these must be preceded by a dollar sign, hence the
transition to q4. Here q5 represents a positive number (no leading 0s) and q6 represents 0. These
states are accept states, to satisfy case (1). Case (2) requires representation for cents. States q8, and
q9 process the cents, and q7 processes the decimal point. Notice q8 is not an accept state, but q9 is,
since there must be 2 digits in the cents value. There are transitions from q5 and q6 to q7 to connect
the dollars with the cents, and thus satisfy case (2).
(part b) Write a regular expression for the set of valid currency amounts.
Solution
The regular expression is ([1-9]|?)[0-9]c | $(0|[1-9][0-9]*)(?|.[0-9][0-9]) where [0-
9]=(0|1|2|3|4|5|6|7|8|9) and [1-9]=(1|2|3|4|5|6|7|8|9)
Explanation: Break the expression down into the accept states.
- q4 is the cents representation, and represents (0|[1-9]|[1-9][0-9])c = ([0-9]|[1-9][0-9])c = ([1-
9]|?)[0-9]c
- q5 represents $[1-9][0-9]*, and q6 represents $0, so q5|q6 = $(0|[1-9][0-9]*)
- q9 is q5 or q6, followed by .[0-9][0-9], so q9 = $(0|[1-9][0-9]*).[0-9][0-9]
- q5|q6|q9 = (q5|q6)|(q5|q6).[0-9][0-9], and so can be written as (q5|q6)(?|.[0-9][0-9])
Therefore, the final expression is q4|(q5|q6|q9) = ([1-9]|?)[0-9]c | $(0|[1-9][0-9]*)(?|.[0-9][0-9])
Problem 2
Here is the NFA is graphical form:
Solution
Notice that {p,q}, {p,r}, {p,s}, {p,r,s}, {p,q,s}, and {p,q,r,s} are not reachable from the start state,
and are thus not included in the DFA.
Problem 3
Part a) Final digit appeared before
We first guess which digit is going to be the last one, and we do that by having epsilon transitions to
the ten "guess" states above. Then we look for an occurence of the digit we guessed in the middle of
the string. When we find one, we go to the respective "found" state. After we have found the
proposed last digit in the middle of the string, we must confirm that our guess is correct. Each
"found" state has a loop around itself for every character so that we can read the rest of the string.
When we run into the digit we guessed, it just might be the last digit, so we have an outgoing arc
labeled with that digit going to the "Must be last" state. Note that when we run into the character we
guessed, we can either follow the ? arc or the outgoing arc. This accounts for the fact that any
occurence of the guessed digit could come either in the middle of the string or at the end. At the
"Must be last" state, we will exit if we read any more characters. If we don't find any more
characters, we have confirmed our guess and hence "Must be last" is the accepting state.

Textul de mai sus reprezinta un extras din "Limbaje Formale si Automate". Pentru versiunea completa a documentului apasa butonul Download si descarca fisierul pe calculatorul tau. Prin descarcarea prezentei lucrari stiintifice, orice utilizator al site-ului www.studentie.ro declara si garanteaza ca este de acord cu utilizarile permise ale acesteia, in conformitate cu prevederile legale ablicabile in domeniul proprietatii intelectuale si in domeniul educatiei din legislatia in vigoare.

In cazul in care intampini probleme la descarcarea fisierului sau documentul nu este nici pe departe ceea ce se doreste a fi te rugam sa ne anunti. Raporteaza o eroare

Important!

Referatele si lucrarile oferite de Studentie.ro au scop educativ si orientativ pentru cercetare academica.

Iti recomandam ca referatele pe care le downloadezi de pe site sa le utilizezi doar ca sursa de inspiratie sau ca resurse educationale pentru conceperea unui referat nou, propriu si original.

Alti utilizatori au mai cautat: CURSCALCULATOAREAutomatelimbaje de programare
Jacheta usoara verde oliv inchis Jacheta usoara verde oliv inchis Descriere produs:Tip: jachetaCuloare: verde oliv inchisMaterial: usorDetalii: margini...
Jacheta usoara violet inchis Jacheta usoara violet inchis Descriere produs:Tip: jachetaCuloare: violet inchisMaterial: usorDetalii: margini...
Camasa alba in dungi Camasa alba in dungi Descriere produs:- camasa alba cu dungi albastre- imprimeu text pe partea din spate- guler...