!!! aug !!! Dla języków podaj wzorce/wyraż reg



Pobieranie 11.61 Kb.
Data04.05.2016
Rozmiar11.61 Kb.
!!! AUG !!!

  1. Dla języków podaj wzorce/wyraż reg.:

# {x:x zaw. parzystą liczbę „a”} (b*ab*ab*)*

# {x:x zaw. nieparzystą liczbę „a”} (b*ab*ab*)*ab*

  1. Podaj wzorce/w.r. opisujące język złożony z:

# nad alf.{a,b} które nie mają podsł. „aa” (b|ab)*(a|E)

# nad alf{a,b,c} ---------;;----------- ([^a] |a[^a])*(a|E)

# {a,b} nie mają „bbab” (a|b)*bbab(a|b)* lub .*bbab.*

# {a,b} które nie zawierają podsł. „ab” b*a*

# {a,b,c} złożonych z 1 rodzaju symboli a*|b*|c*

# {a,b,c} złoż. co najw. z 2 rodz. symb. (a|b)*|(b|c)*|(a|c)*



# {a,b} – słowa o parz a i b (aa|bb|(ba|ab)(aa|bb)*(ab|ba))*

  1. Opisz języki reprezentowane przez wyrażenia reg.:

# (11|0)*(00|1)* 1naw-1.wyst. parami; 2 naw-0 wyst. parami

#(1|01|001)*(E|0|00) Język nad {a,b}w którym nie ma 3 ”0”



  1. Porównaj wyr. reg. pod wzgl. zawierania się:

# 0*|1*€(0|1)* ;; Ǿ*= E* ;; (0*1)*€(0*1*)* ;; α(βα)*=( αβ)*α

  1. α=(a|b)*ab(a|b)*. Podaj wzorzec dla (nie!)L(α) jeśli:

# ∑={a,b} b*a* (nie zawiera „ab”)

# ∑={a,b,c} b*a*|.*c.*




  1. Czy aabaab,aaaaba,aabbaa,abaaba należą do gram.?

# S->ABS|AB ; A->Aa|Aa ; B->bA

aaaaba S->AB->aAB->aaAB->aaaAB->aaaaB->aaaabA…

# S->aB|Ab|SS ; A->As|As ; B->Sb|b dla aabbab niejedn.


  1. Podaj gramatykę generującą język:

# {anbm:n=2m} S->AX A->Aa|E X->aaXb|E

# { anbn} S->aSb|E

# { ai b j ci :i,j nal.N} S->aSc|B S->bB|E

# { ai b j aj b i :i,j nal.N} S->aSb|X X->bXa|E

# { ai b j c k : i !=j lub j!=k} S->XC|AY; X->aAT|TBb;

C->Cc|E;A->aA|E;Y->bBV|VCc;V->bVc|E;B->bB|E...

#{ ai b j ck : j=i+k}={ ai b i+k ak}= {ai bi bk ak}



S->XY ; X->aXb|E ; Y->bYa|E

  1. Gramatyka dla wyr. nawiasowych:

# Tylko dla(): S->(S)|SS|SNY

# Dla {},[],(): S->(S)|{S}|[S]|SS|E

#Z prio. W() są (); w[] są () lub []; w {} cokolwiek:

S->{S}|A|SS; A->[A]|B|AA; B->(B)|E|BB

#j.w. ale w {} tylko {} lub[]: S->w|k|o|SS ;

w->{w}|ww|[k]|[k][k]|E; k->[k]|kk|o; o->(o)|oo|E

  1. Jaki język generuje gramatyka?

# S->aAz|ZBb {anbm : n!=m}

# Z->aZb|E {anbn : n>=0}

# A->aA|E {an : n>=0}

#B->Bb|E {bn : n>=0}



  1. Gramatyka dla palindromów np.abba,aba,aabaa

#S->Asa|BSb|a|b|E

#Dla pal. parz dł.: S->aSa|bSb|E


  1. Wzorzec/wyr.reg nad {ab} dla:

# przed „a” zawsze jest „b” (b*|ba)*

#ilosc „a” po dziel.na3 daje 2: (b*ab*ab*)(ab*ab*ab*)*

  1. Gramatyka dla języka { ai b j c k : i + j >=k}

S -> X | Y; X -> AB; A -> aA | a | BBC; B -> bBc |bc;
Y -> aYc | aGc | aXc ; G -> bG | b | E

  1. Gram. dla języka {wR ai wbj:w nal.{a,b}*;i+j=1(mod2)}

S -> WX | YZ; W -> aWa | bWb | cWc | D; D -> aaD | a
X ->bbX|E; Y->aYa|bYb|cYc|A ;A ->aaA|E; Z ->bbZ|b
: 6sem -> AUG -> AUG




©absta.pl 2019
wyślij wiadomość

    Strona główna