2013-11-07, 11:47
  #1
Medlem
adequates avatar
I en vild gissning att teoretisk datavetenskap hör hemma under matematik: En sak jag inte har förstått är hur klassen kontextfria språk kan vara en delmängd till klassen kontextkänsliga språk. Jag är helt och hållet med på hur de formellt definieras, men hur ska man tänka rent intuitivt? Att de kontextkänsliga kan vara känsliga för kontext, men är det inte nödvändigtvis, vilket är fallet för de kontextfria? Eller har jag fått något om bakfoten?
Citera
2013-11-07, 12:01
  #2
Medlem
MeanMEs avatar
Läs The hierarchy, delen i:

http://en.wikipedia.org/wiki/Chomsky_hierarchy
__________________
Senast redigerad av MeanME 2013-11-07 kl. 12:04.
Citera
2013-11-07, 14:27
  #3
Medlem
Citat:
Ursprungligen postat av adequate
Att de kontextkänsliga kan vara känsliga för kontext, men är det inte nödvändigtvis, vilket är fallet för de kontextfria?
Så uppfattar jag det. Det kan jämföras med funktioner. Generellt gäller att deras värde är känsligt för argumentet, men så finns ju konstanta funktioner.
Citera
2013-11-07, 16:17
  #4
Medlem
adequates avatar
Citat:
Ursprungligen postat av manne1973
Så uppfattar jag det. Det kan jämföras med funktioner. Generellt gäller att deras värde är känsligt för argumentet, men så finns ju konstanta funktioner.
Aha! Bra tänkt, den liknelsen tänkte jag inte alls på tbh.
Citera
2013-11-07, 16:37
  #5
Medlem
matteyass avatar
Du kan säkert hålla med om att vi kan skapa två mängder A och B vars medlemmar sorteras enligt "kontextkänsliga" och "ej kontextkänsliga" och sen gäller det att varken A eller B är en delmängd av den andra.

Däremot finns det ingenting motsägelsefullt att vi tar mängden A från ovan exempel (kontextkänsliga) och sen kan skapa två (ej tomma) delmängder C och D vars medlemmar sorteras enligt "har kontext" och "saknar kontext."
Citera
2013-11-08, 09:48
  #6
Medlem
srinivasas avatar
Vet absolut inget om detta, men av definitionen verkar det som om kontextfria verkligen är en äkta delmängd av de kontextkänsliga. Har jag missförstått definitionerna?
Citera
2013-11-08, 10:52
  #7
Medlem
Citat:
Ursprungligen postat av srinivasa
Vet absolut inget om detta, men av definitionen verkar det som om kontextfria verkligen är en äkta delmängd av de kontextkänsliga. Har jag missförstått definitionerna?
Precis som de konstanta funktionerna är en äkta delmängd av mängden av samtliga funktioner.
Citera

Skapa ett konto eller logga in för att kommentera

Du måste vara medlem för att kunna kommentera

Skapa ett konto

Det är enkelt att registrera ett nytt konto

Bli medlem

Logga in

Har du redan ett konto? Logga in här

Logga in