Moin,
frage hier mal nach, da ds.de best und hier auch einige Informatik studieren.
Hab ein paar Fragen zu dem Thema formale Sprachen.
Und zwar haben wir in einer Aufgabe mehrere Sprachen gegeben und sollen zeigen, ob es einen DFA gibt (oder nicht), der die Sprache L1, L2, usw. entscheidet.
Nun bezieht sich meine Frage auf die Vorgehensweise bei solchen Aufgaben:
Sei L := { w | Das vorletzte Zeichen von w ist 7} wobei 7 (natürlich) im Alphabet ist.
Das diese Sprache von einem DFA entschieden werden kann, ist mir klar.
-Reicht es als Beweis aus, einen DFA als 5-Tupel oder als Graphen anzugeben?
-Reicht es, eine reguläre Grammatik G anzugeben, sodass L = L(G) ist? Wir hatten in der Vorlesung gezeigt, dass jede reguläre Sprache von einem DFA entschieden werden kann.
-Oder stumpf beweisen (z.B. mit dem Pumping-Lemma).
Dann habe ich hier noch die Sprache L := { w | w ist Dezimaldarstellung einer durch 43 teilbaren Zahl }.
Wie zeigt man ohne evtl. Teilbarkeitsregeln (ich kenne zumindest keine für 43), dass es einen DFA gibt, der L entscheidet (intuitiv würde ich zumindest behaupten, dass es einen gibt, weil es auch einen für L := { w | w ist Dezimaldarstellung einer durch 3 teilbaren Zahl } gibt).
DFA = DEA; NFA = NEA für die Deutschen.
Würde mich über Antworten freuen.
frage hier mal nach, da ds.de best und hier auch einige Informatik studieren.
Hab ein paar Fragen zu dem Thema formale Sprachen.
Und zwar haben wir in einer Aufgabe mehrere Sprachen gegeben und sollen zeigen, ob es einen DFA gibt (oder nicht), der die Sprache L1, L2, usw. entscheidet.
Nun bezieht sich meine Frage auf die Vorgehensweise bei solchen Aufgaben:
Sei L := { w | Das vorletzte Zeichen von w ist 7} wobei 7 (natürlich) im Alphabet ist.
Das diese Sprache von einem DFA entschieden werden kann, ist mir klar.
-Reicht es als Beweis aus, einen DFA als 5-Tupel oder als Graphen anzugeben?
-Reicht es, eine reguläre Grammatik G anzugeben, sodass L = L(G) ist? Wir hatten in der Vorlesung gezeigt, dass jede reguläre Sprache von einem DFA entschieden werden kann.
-Oder stumpf beweisen (z.B. mit dem Pumping-Lemma).
Dann habe ich hier noch die Sprache L := { w | w ist Dezimaldarstellung einer durch 43 teilbaren Zahl }.
Wie zeigt man ohne evtl. Teilbarkeitsregeln (ich kenne zumindest keine für 43), dass es einen DFA gibt, der L entscheidet (intuitiv würde ich zumindest behaupten, dass es einen gibt, weil es auch einen für L := { w | w ist Dezimaldarstellung einer durch 3 teilbaren Zahl } gibt).
DFA = DEA; NFA = NEA für die Deutschen.
Würde mich über Antworten freuen.