[Gramatyki] Języki rekurencyjne i rekurencyjnie przeliczalne

[piotru64]

Witam, potrzebuje pomocy przy rozwiązaniu takiego zadania:

Niech \(\displaystyle{ L}\) będzie pewnym językiem z \(\displaystyle{ RE - R}\), gdzie \(\displaystyle{ R}\)oznacza zbiór jezyków rekurencyjnych , a \(\displaystyle{ RE}\) jezyków rekurencyjnie przeliczalnych.Niech \(\displaystyle{ L'}\) oznacza podzbiór \(\displaystyle{ L}\) zawierajacy wyłącznie słowa długości nieparystej, a \(\displaystyle{ L''}\) wyłacznie słowa długości parzystej. \(\displaystyle{ L = L' \cup L''}\)

*Pokazać że przynajmniej jeden z \(\displaystyle{ L', L''}\) nie należy do\(\displaystyle{ R}\)
*Podać przykład takiego\(\displaystyle{ L}\), że \(\displaystyle{ L'' \in R}\) a \(\displaystyle{ L'}\) nie należy do \(\displaystyle{ R}\)
*Podać przykład takiego \(\displaystyle{ L}\), że \(\displaystyle{ L'}\) oraz \(\displaystyle{ L''}\) nie należą do \(\displaystyle{ R}\)

[Kartezjusz]

Może Cię źle rozumiem, ale z samej definicji \(\displaystyle{ L}\) oba nie należą co \(\displaystyle{ R}\)

[piotru64]

Może Cię źle rozumiem, ale z samej definicji \(\displaystyle{ L}\) oba nie należą co \(\displaystyle{ R}\)

Mógłbyś rozwinąć? Chodzi o to: \(\displaystyle{ L}\) będzie pewnym językiem z \(\displaystyle{ RE - R}\)?

[Dasio11]

(a) Suma dwóch języków rekurencyjnych jest językiem rekurencyjnym, więc gdyby \(\displaystyle{ L'}\) i \(\displaystyle{ L''}\) były rekurencyjne, to \(\displaystyle{ L = L' \cup L''}\) też.

(b) Wystarczy wymyślić język \(\displaystyle{ L' \in RE \setminus R}\) spełniający założenia i wziąć \(\displaystyle{ L'' = \{ \text{wszystkie słowa długości parzystej} \},}\) bo wtedy automatycznie \(\displaystyle{ L = L' \cup L'' \in RE \setminus R.}\)

[Nikak]

Podpinam się do prośby o pomoc.

(a) Suma dwóch języków rekurencyjnych jest językiem rekurencyjnym, więc gdyby \(\displaystyle{ L'}\) i \(\displaystyle{ L''}\) były rekurencyjne, to \(\displaystyle{ L = L' \cup L''}\) też.

(b) Wystarczy wymyślić język \(\displaystyle{ L' \in RE \setminus R}\) spełniający założenia i wziąć \(\displaystyle{ L'' = \{ \text{wszystkie słowa długości parzystej} \},}\) bo wtedy automatycznie \(\displaystyle{ L = L' \cup L'' \in RE \setminus R.}\)

Rozumiem, że język \(\displaystyle{ L}\) powinien być językiem rekurencyjnie przeliczalnym, ale nie rekurencyjnym.

• Z pkt 1 wszystko jest jasne, bo wynika to z właściwości języków rekurencyjnych.
• Jeśli chodzi o pkt 2: należy wymyślić taki język, dla którego \(\displaystyle{ L' \notin R, a \ L'' \in R}\)
  myślałam o tym, że język \(\displaystyle{ L''}\) mógł by być pusty, był by wtedy regularny, a znaczy i rekurencyjny, no a język \(\displaystyle{ L' \notin R}\) powinien być zbiorem słów o długości nieparzystej
• No i pkt 3: \(\displaystyle{ L' \notin R \ oraz \ L'' \notin R}\)

Ogólnie, nie wiem od czego zacząć wymyślanie tych przykładowych języków.