Informatiker Board | Theoretische Informatik | Kann mir jemand zeigen dass REG echte Teilmenge von L

Informatiker Board » Themengebiete » Theoretische Informatik » Kann mir jemand zeigen dass REG echte Teilmenge von L

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Kann mir jemand zeigen dass REG echte Teilmenge von L

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

HelpMePlease
Grünschnabel

Dabei seit: 22.01.2015
Beiträge: 4

Kann mir jemand zeigen dass REG echte Teilmenge von L

Zitatantwort auf diesen Beitrag erstellen

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

Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von HelpMePlease: 22.01.2015 15:31.

22.01.2015 15:29

Nehmen Sie HelpMePlease in Ihre Freundesliste auf

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Was ist REG und was ist L?

Gruß,

Karlito

22.01.2015 15:56

Nehmen Sie Karlito in Ihre Freundesliste auf

HelpMePlease
Grünschnabel

Dabei seit: 22.01.2015
Beiträge: 4

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:14

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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. $[latex]\mathcal{L} = \{a^nb^n | n \in \mathbb{N} \}[/latex]$ ). 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 $[latex]REG \subset L[/latex]$ gelten.

Gruß,

Karlito

22.01.2015 16:27

HelpMePlease
Grünschnabel

Dabei seit: 22.01.2015
Beiträge: 4

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 16:59

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

22.01.2015 17:04

HelpMePlease
Grünschnabel

Dabei seit: 22.01.2015
Beiträge: 4

OK,

L ist die Bezeichnung für den logarithmischen Platz, also doch im Zusammenhang mit Komplexitätsklassen.

23.01.2015 02:02

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Kann mir jemand zeigen dass REG echte Teilmenge von L