Adjatok CF (környezetfüggetlen) grammatikát az alábbi nyelvekhez: 

1. {aⁿ b^k cⁿ| n, k 1, k=n mod 5}

2. {ww^-1 | w  {a,b}^*}

3. {a^m bⁿ | m  n 2m} 

4.{aⁱ b^j c^k | i < j vagy j < k}

5. Az S  SS | (S)  |  grammatika a helyes zárójelezéseket generálja, azaz azokat a (-bõl és )-bõl álló szavakat, ahol a nyitó és a záro zárójelek száma ugyanannyi és a szó minden prefixében (kezdõszelet) legala'bb annyi kezdõjel van, mint záró.
 

Adjatok véges automatát az alábbi nyelvekhez! Determinisztikusat vagy ha csak nemdeterminisztikus sikerül, akkor csinaljatok belõle determinisztikusat.

1. 
{w  {a,b}^* |  |w|_a osztható hárommal,|w|_b páros }
Itt a |w|_a a w-ben levõ a-k számát jelöli.

2.
{w  {a,b}^* |  a w-beli homogén a-sorozatok oszthatók hárommal, a homogén b-sosrozatok meg kettõvel}
Pl.az abaab nem jó, mert a homogén sosrozatai: a, b, aa, b.

3. 
{(1111)⁺w | w  {0,1}^*}
A + a kitevõben azt jelenti, hogy legalább egyszer. 

4.
{w  {a,b}^*| w-ben hátulról a harmadik betù b}
Figyelem! Hátulról!

5.
{w  {a,b}^*| w bináris számként tekintve öttel osztható}

6.
Adjatok olyan reguláris nyelvtant, ami az   {, w₁, ..., w_n} véges nyelvet generálja!

7.  
Adott az alábbi  függvénnyel definiált automata, végállapota a D, kezdõállapota az A.
(A,0)=A
(A,1)=B 
(B,0)=C
(B,1)=B 
(C,0)=A
(C,1)=D
(D,0)=A
(D,1)=B 

Mit ismer ez fel?

8. 
Adott az alábbi  függvénnyel definiált automata, végállapota a B, kezdõállapota az A.
(A,0)=A,B
(A,1)=B 
(B,0)=A
(B,1)=B 

És ez mit ismer fel?
Ez ugye nemdeterminisztikus, csináljatok belõle detreminisztikust (gyakorlásnak jó).