Struktur Diskrit : Ekspresi Reguler dan Pengenal Language
Language Recognition
We have seen that finite-state automata can be used as language recognizers. What sets can be recognized by these machines?
Kleene (1956) showed that there is a finite-state automaton that recognizes a set if and only if this set can be built up from the null set, the empty string, and singleton strings by taking concatenations, unions, and Kleene closures, in arbitrary order. Sets that can be built up in this way are called regular sets.
To define regular sets we first need to define regular expressions.
Regular Expression
Examples
What are the strings in the regular sets specified by the regular expressions 10∗, (10)∗, 0 ∪ 01, 0(0 ∪ 1)∗, and (0∗1)∗ ?
Find a regular expression that specifies each of these sets:
- the set of bit strings with even length
- the set of bit strings ending with a 0 and not containing 11
- the set of bit strings containing an odd number of 0s
Construct a nondeterministic finite-state automaton that recognizes the language generated by the regular grammar G = (V, T, S, P), where V = {0, 1,A, S}, T = {0, 1}, and the productions in P are S → 1A, S → 0, S → λ, A → 0A, A → 1A, and A → 1.
Find a regular grammar that generates the regular set recognized by this finite-state automaton:
Sumber
Slide Strukdis : Regular Expression
Posting Komentar