|
| "Closure" egenskaber for regulære og konte~ Fra : Preben Holm |
Dato : 12-01-05 22:47 |
|
Hej alle
Så vidt jeg erindrer gælder:
Regulære sprog er lukkede under:
- union
- concatenation
- kleene star
- complementation
- intersection
Kontekstfrie sprog er lukkede under:
- union
- concatenation
- kleene star
- intersection med regulære sprog
Ikke lukkede under:
- complementation
- intersection
Er dette korrekt?
Gælder der andre "closure"-egenskaber ved regulære og kontekst-frie
sprog som jeg har glemt i min oversigt!
Mvh / Preben Holm
| |
Torben Ægidius Mogen~ (13-01-2005)
| Kommentar Fra : Torben Ægidius Mogen~ |
Dato : 13-01-05 11:07 |
|
Preben Holm <64bitNOnoSPAMno@mailme.dk> writes:
> Så vidt jeg erindrer gælder:
>
> Regulære sprog er lukkede under:
> - union
> - concatenation
> - kleene star
> - complementation
> - intersection
>
> Kontekstfrie sprog er lukkede under:
> - union
> - concatenation
> - kleene star
> - intersection med regulære sprog
>
> Ikke lukkede under:
> - complementation
> - intersection
>
> Er dette korrekt?
Ja.
> Gælder der andre "closure"-egenskaber ved regulære og kontekst-frie
> sprog som jeg har glemt i min oversigt!
Regulære og kontekstfri sprog er også lukkede under, præfiks, suffix,
delstreng, delfølge og baglæns læsning. De er ikke lukkede under
anagramdannelse (omordning af tegn i en tegnfølge).
Torben
| |
Preben Holm (13-01-2005)
| Kommentar Fra : Preben Holm |
Dato : 13-01-05 17:21 |
|
> Regulære og kontekstfri sprog er også lukkede under, præfiks, suffix,
> delstreng, delfølge og baglæns læsning. De er ikke lukkede under
> anagramdannelse (omordning af tegn i en tegnfølge).
Præfiks, suffix? Hvordan som operation?
Delfølge?
Hvad hedder iøvrigt
R\L? - altså R uden/minus L
F.eks. Sigma*\{a}
Ingen af dem jeg læser til eksamen med aner hvad det egentlig hedder som
operation!
Mvh / Preben Holm (som skal til eksamen lørdag)
| |
Torben Ægidius Mogen~ (13-01-2005)
| Kommentar Fra : Torben Ægidius Mogen~ |
Dato : 13-01-05 18:03 |
|
Preben Holm <64bitNOnoSPAMno@mailme.dk> writes:
> > Regulære og kontekstfri sprog er også lukkede under, præfiks, suffix,
> > delstreng, delfølge og baglæns læsning. De er ikke lukkede under
> > anagramdannelse (omordning af tegn i en tegnfølge).
>
> Præfiks, suffix? Hvordan som operation?
Præfiks af en tegnfølge er en indledende del af denne, suffiks er en
afsluttende del.
> Delfølge?
Fås ved at slette vilkårlige tegn i følgen.
> Hvad hedder iøvrigt
> R\L? - altså R uden/minus L
>
> F.eks. Sigma*\{a}
>
> Ingen af dem jeg læser til eksamen med aner hvad det egentlig hedder
> som operation!
Differerensmængde. R\L = R fælles med komplementet til L, så hvis
klassen er lukket under komplement og fællesmængde følger lukkethed
under differensmængde. Fællesmængde følger endvidere af
foreningsmængde og komplement.
Torben
| |
Jens Axel Søgaard (13-01-2005)
| Kommentar Fra : Jens Axel Søgaard |
Dato : 13-01-05 21:23 |
|
>>Hvad hedder iøvrigt
>> R\L? - altså R uden/minus L
>>
>>F.eks. Sigma*\{a}
>>
>>Ingen af dem jeg læser til eksamen med aner hvad det egentlig hedder
>>som operation!
> Differerensmængde. R\L = R fælles med komplementet til L, så hvis
> klassen er lukket under komplement og fællesmængde følger lukkethed
> under differensmængde. Fællesmængde følger endvidere af
> foreningsmængde og komplement.
Man plejer at udtale R\L som "R fraregnet L".
--
Jens Axel Søgaard
| |
Stefan Holm (13-01-2005)
| Kommentar Fra : Stefan Holm |
Dato : 13-01-05 21:54 |
|
Jens Axel Søgaard <usenet@soegaard.net> writes:
> Man plejer at udtale R\L som "R fraregnet L".
Eller "R skåret L".
--
Stefan Holm
"I'm for whichever party does the mouth-shooting."
| |
|
|