Teori Komputasi

1. Berikan sebuah Tata Bahasa (Grammar) atas alpahabet {a, b} yang membentuk bahasa

L={w | w berisi string yang mempunyai sejumlah sama a dan b}

2.  Tentukan sebuah Tata Bahasa Bebas Konteks (Context Free Grammar) atas {0, 1}  yang menghasilkan bahasa

L={w | w berisi string yang banyaknya 0 adalah dua kali lipat banyaknya 1}

3. Tentukan sebuah Tata Bahasa sensitive context (Context Sensitive Grammar) yang membentuk bahasa

L={a^p  | p adalah bilangan prima}

4. Diketahui V_N={D}, V_T={d, +, -} dan diberikan tata bahasa dengan mesin Produksi adalah

P={D -> D-D++D-D ; D -> d ; + -> + ; - -> -}

jika simbol d menyatakan perintah menggambarkan garis lurus dengan panjang tertentu dan arah tertentu yang dimulai dari suatu titik horizontal ke arah kanan, simbol + menyatakan perintah merubah arah garis 60 derajat ke kanan dan simbol - menyatakan perintah merubah arah garis 60 derajat ke kiri, maka pola gambar seperti apa yang mungkin dapat dibuat? Gambarkan!

Program menggunakan Phyton

function tugastekom

fprintf ('  Tugas Teori Komputesi\n\n');

while 1

x=input('masukkan nomor soal(1-4): ');

if x==1

    fprintf('mengecek sejumlah sama a dan b\nmasukkan karater: ');

    y=input('','s');

    if sum(y=='a')==sum(y=='b')&&sum(y=='a')+sum(y=='b')==length(y)

        fprintf('DATA DITERIMA dengan jumlah ab=%i \n',length(y)/2)

    else

        fprintf('DATA DITOLAK karena a=%i, b=%i, selain a-b=%i\n',sum(y=='a'),sum(y=='b'), length(y)-sum(y=='a')-sum(y=='b'))

    end

elseif x==2

    fprintf('mengecek sejumlah 0 dua kali jumlah 1\nmasukkan karakter: ');

    y=input('','s');

    if sum(y=='0')==2*sum(y=='1')&&sum(y=='0')+sum(y=='1')==length(y)

        fprintf('DATA DITERIMA dengan jumlah 0=%i, jumlah 1=%i \n', sum(y=='0'), sum(y=='1'))

    else

        fprintf('DATA DITOLAK karena 0=%i, 1=%i, selain 0-1= %i\n', sum(y=='0'), sum(y=='1'), length(y)-sum(y=='0')-sum(y=='1'))

    end

elseif x==3

     fprintf('mengecek sejumlah a prima\nmasukkan karakter: ');

     y=input('','s');

    z=1;

    if length(y)>1

        z=0;

        for q=2:length(y)^.5

            if ~mod(length(y),q)

                z=1;

                break;

            end

        end

    end

    if z||sum(y=='a')~=length(y)

        fprintf('DATA DITOLAK karena a=%i, selain a sebanyak = %i\n', sum(y=='a'), length(y)-sum(y=='a'))

    else

        fprintf('DATA DITERIMA dengan jumlah a=%i, a sejumlah prima\n', sum(y=='a'))

    end

elseif x==4

    fprintf('mengecek bahasa d-d++d-d yang bersesuaian\nmasukkan karakter: ');

    y=input('','s');

    if sum(y=='+')~=sum(y=='-')||mod(sum(y=='-'),2)||mod(sum(y=='+'),2)||sum(y=='d')-1~=3*sum(y=='+')/2||sum(y=='d')+sum(y=='+')+sum(y=='-')~=length(y)

        fprintf('DATA DITOLAK karena tidak sesuai dengan d-d++d-d\n')

    else

        z=0;

        if y(1)=='d'

            z=1;

            for q=1:length(y)-1

                if y(q)=='d';

                    if y(q+1)~='-'&&y(q+1)~='+'

                        z=0;

                        break;

                    end

                elseif y(q)=='+'

                    if y(q-1)~='d'&&y(q+1)=='+'||y(q-1)~='+'&&y(q+1)=='d'

                        z=0;

                        break;

                    end

                elseif y(q)=='-'

                    if (y(q-1))~='d'

                        z=0;

                        break;

                    end

                end

            end

        end

        if z

            while length(y)~=1

                if sum(y(length(y)-6:length(y))=='-d++d-d')==7

                    y=y(1:length(y)-7);

                elseif sum(y(1:7)=='d-d++d-')==7

                    y=y(8:length(y));

                elseif sum([y(1:2) y(length(y)-4:length(y))]=='d-++d-d')==7

                    y=y(3:length(y)-5);

                elseif sum([y(1:5) y(length(y)-1:length(y))]=='d-d++-d')==7

                    y=y(6:length(y)-2);

                else

                    break;

                end

            end

        end

        if length(y)~=1||~z

            fprintf('DATA DITOLAK karena tidak sesuai dengan d-d++d-d\n')

        else

            fprintf('DATA DITERIMA \n')

        end

    end

else

    fprintf('format tidak dikenal\n')

end

x=input('ulangi atau tidak?(y/t): ','s');

if 'Y'==x||'y'==x

    fprintf('\n')

else

    fprintf('\n')

    break;

end

end

end