10 KiB
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