Kann mir jemand zeigen dass REG echte Teilmenge von L |
22.01.2015, 15:29 | Auf diesen Beitrag antworten » |
HelpMePlease | Kann mir jemand zeigen dass REG echte Teilmenge von L Hallo werte Experten der theoretischen Informatik, kann mir jemand verständlich zeigen bzw erklären wieso REG eine echte Teilmgenge von L ist ? Vielen Dank Im Vorraus |
|
|
22.01.2015, 15:56 | Auf diesen Beitrag antworten » |
Karlito | Was ist REG und was ist L? Gruß, Karlito |
22.01.2015, 16:14 | Auf diesen Beitrag antworten » |
HelpMePlease | REG ist die Klasse der regulären Sprachen und L bezeichnet meiner Meinung nach die Komplexitätsklassen de.wikipedia.org/wiki/L_%28Komplexitätsklasse%29 |
22.01.2015, 16:27 | Auf diesen Beitrag antworten » |
Karlito | OK, ich gehe davon aus, dass das nichts mit Komplexitätsklassen zu tun hat sondern es geht nur um die Frage, warum die regulären Sprachen eine echte Teilmenge aller (formalen) Sprachen ist. Die Begründung ist meiner Meinung nach relativ einfach: reguläre Sprachen sind nur diejenigen Sprachen, welche von einem endlichen Automaten erkannt werden. Es gibt jedoch auch noch Sprachen, welche nicht von endlichen Automaten akzeptiert werden (z.B. ). Da alle regulären Sprachen in der Menge der Sprachen enthalten sind, jedoch die Menge aller Sprachen größer ist, als die Menge der regulären Sprachen, muss gelten. Gruß, Karlito |
Anzeige | |
|
|
22.01.2015, 16:59 | Auf diesen Beitrag antworten » |
HelpMePlease | erstmal danke für die schnelle antwort und die soweit sehr einleuchtende erklärung, ich werde mich erkundigen, ob es wirklich nur um die formalen sprachen geht oder doch um etwas anderes und notfalls nochmals ergänzen |
22.01.2015, 17:04 | Auf diesen Beitrag antworten » |
Karlito | OK |
23.01.2015, 02:02 | Auf diesen Beitrag antworten » |
HelpMePlease | OK, L ist die Bezeichnung für den logarithmischen Platz, also doch im Zusammenhang mit Komplexitätsklassen. |
|