0 Daumen
360 Aufrufe

Die Sprache \( L_{1}=\left\{a^{i} b^{j} \mid i \cdot j\right. \) ist Primzahl und \( \left.i, j>1\right\} \) ist nicht regulär.


\( L_{1} \) nicht regulär: Wir nehmen Primzahlen \( p \) und \( q \) mit \( i \cdot j=p<q \) und \( d=q-p \) für sinnvolle \( i, j>1 \). Dann aus Vorlesung: Es existiert \( n \) mit \( p+n d \) prim und \( p+(n+1) d=q+n d \) nicht prim. Also ist der Index unendlich. Also \( L \) nicht regulär und Aussage wahr.



ich habe einen Beweis zur obigen Sprach verfasst, kann man so beweisen, dass eine Sprache regulär ist ?

Avatar von

1 Antwort

0 Daumen
 
Beste Antwort

Wenn \(i\cdot j\) eine Primzahl ist, dann ist \(i=1\vee j=1\). Somit ist \(L_1=\emptyset\) und somit regulär.

Avatar von 5,7 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community