DJFZ-2023/lab-01/lab-01.ipynb

Języki formalne i złożoność obliczeniowa

Część 1: Wprowadzenie do Pythona: Listy i Słowniki

Listy

# Definicja listy
lista = [1, 2, 3, 4, 5]

# Dodawanie elementu na koniec listy
lista.append(6)

# Usuwanie elementu z listy
lista.remove(3)

# Wyciąganie i zwracanie ostatniego elementu z listy
element = lista.pop()

print(lista)
print(element)

# Prosta funkcja, która zwraca długość ciągu znaków
def dlugosc_ciagu(s):
    return len(s)

# Testowanie funkcji
print(dlugosc_ciagu("Hello"))  # Powinno zwrócić 5

5

# Funkcja, która sprawdza, czy dany ciąg znaków kończy się na danym sufiksie
def konczy_sie_na(s, sufiks):
    return s.endswith(sufiks)

# Testowanie funkcji
print(konczy_sie_na("Automat", "mat"))  # Powinno zwrócić True
print(konczy_sie_na("Automat", "tom"))  # Powinno zwrócić False

lista = ["a", "b", "c"]
for indeks, wartość in enumerate(lista):
    print(indeks, wartość)

lista1 = [1, 2, 3]
lista2 = ["a", "b", "c"]
for liczba, litera in zip(lista1, lista2):
    print(liczba, litera)

kwadraty = [x**2 for x in range(10)]
print(kwadraty)

Zadanie 1:

Stwórz listę alfabet, która będzie zawierać litery alfabetu od 'a' do 'z'. Następnie stwórz listę stany, która będzie zawierać stany automatu w postaci "q0", "q1", ..., "q25". Wykorzystaj pętlę for oraz funkcję range() do generowania listy stany. Wykorzystaj list comprehension

print(ord(a))

A

Słowniki

Słowniki w Pythonie to nieuporządkowane kolekcje par klucz-wartość. Klucze w słowniku muszą być unikalne.

# Definicja słownika
slownik = {
    "klucz1": "wartość1",
    "klucz2": "wartość2",
    "klucz3": "wartość3"
}

# Dodawanie nowej pary klucz-wartość
slownik["klucz4"] = "wartość4"

# Usuwanie pary klucz-wartość
del slownik["klucz2"]

print(slownik)

Zadanie 2:

Stwórz słownik delta, który będzie reprezentować funkcję przejścia dla automatu rozpoznającego ciągi nad alfabetem {a, b}, które kończą się na "ab". Słownik powinien mieć postać:

delta = {}

def akceptuje(delta, ciag, stan_poczatkowy='q0', stan_akceptujacy='q2'):
    stan = stan_poczatkowy
    for symbol in ciag:
        stan = delta[stan][symbol]
    return stan == stan_akceptujacy

# Przykładowy input i output
input1 = "aabb"
output1 = akceptuje(delta, input1)
print(f"Ciąg '{input1}' jest akceptowany: {output1}")  # False, bo kończy się na "bb"

input2 = "aaabaaa"
output2 = akceptuje(delta, input2)
print(f"Ciąg '{input2}' jest akceptowany: {output2}")  # False, bo kończy się na "aa"

input3 = "ab"
output3 = akceptuje(delta, input3)
print(f"Ciąg '{input3}' jest akceptowany: {output3}")  # True, bo to dokładnie ciąg "ab"

Część 2: Implementacja DFA w Pythonie

Definicja DFA

DFA to piątka (Q, Σ, δ, q_0, F), gdzie:

• Q to zbiór stanów
• Σ to alfabet wejściowy
• δ to funkcja przejścia
• q_0 to stan początkowy
• F to zbiór stanów akceptujących

class DFA:
    def __init__(self, Q, Sigma, delta, q0, F):
        self.Q = Q
        self.Sigma = Sigma
        self.delta = delta
        self.q0 = q0
        self.F = F

    def akceptuje(self, string):
        stan = self.q0
        for symbol in string:
            stan = self.delta[stan][symbol]
        return stan in self.F

Zadanie 3: Zaimplementuj automat, który akceptuje ciągi nad alfabetem {a,b}, które mają parzystą liczbę liter a.

Q1 = {}
Sigma1 = {}
delta1 = {
    'q0': {'a': '', 'b': ''},
    'q1': {'a': '', 'b': ''}
}
q01 = ''
F1 = {''}

dfa1 = DFA(Q1, Sigma1, delta1, q01, F1)
print(dfa1.akceptuje("abab"))  # True
print(dfa1.akceptuje("aba"))  # True
print(dfa1.akceptuje("aaab")) # False

Zadanie domowe:

Zadanie 1 (5 pkt):

Zaimplementuj automat deterministyczny, który akceptuje ciągi nad alfabetem {0,1} (liczby binarne), które są podzielne przez 2.

Zadanie 2 (5 pkt):

Automat rozpoznający ciągi z dokładnie trzema literami 'a' Zaimplementuj automat, który akceptuje ciągi nad alfabetem {a,b}, które zawierają dokładnie trzy litery 'a'.

Rozwiązania zadań należy wysłać na adres email: miczar1@amu.edu.pl z tytułem: [DJFZ][NrIndeksu] Zadanie domowe Zajęcia 1. Jako załącznik należy wysłać dwa pliki .py (zadanie1.py, zadanie2.py) z rozwiązaniem. Skrpyty na wejściu mają przyjmować plik tekstowy in.txt i mają zwracać True/False dla każdego wiersza w pliku a następnie zapisać rezultaty do pliku out.txt. Przykładowe wywołanie skryptu: python zadanie1.py in.txt.

Termin wysłania zadań: 27.10.2023 godzina 23:59

Przykładowy plik in.txt:

aaba
aabaa
abab
aaa

Przykładowy plik out.txt:

True
False
False
True