/ Forside / Karriere / Uddannelse / Højere uddannelser / Nyhedsindlæg
Login
Glemt dit kodeord?
Brugernavn

Kodeord


Reklame
Top 10 brugere
Højere uddannelser
#NavnPoint
Nordsted1 1588
erling_l 1224
ans 1150
dova 895
gert_h 800
molokyle 661
berpox 610
creamygirl 610
3773 570
10  jomfruane 570
"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."

Søg
Reklame
Statistik
Spørgsmål : 177560
Tips : 31968
Nyheder : 719565
Indlæg : 6408941
Brugere : 218888

Månedens bedste
Årets bedste
Sidste års bedste