TOC-As-3

1. Construct NPDA’s that recognize the following languages over $Σ = {a, b, c}$ . (10 pt for each)

a. $L_{2} = {a^{n} b^{m} c^{n + m} | n, m \geq 0}$

1-a

b. $L_{3} = {a^{n} b^{n + m} c^{m} | n, m \geq 0}$

1-b

c. $L_{4} = {a^{3} b^{n} c^{n} | n \geq 0}$

1-c

2. Show that the language ${a^{n} | n = 2^{x} f o r a l l x \in N}$ is not contexr-free.

Let $L = {a^{n} | n = 2^{x} f o r a l l x \in N}$

Assume L is context-free.

Let $s = a^{2^{p}}$ which is a string in $L$ .

And $s = w v x y z$

Suppose $w = a^{i}$ , $v = a^{j}$ , $x = a^{k}$ , $y = a^{l}$ , $z = a^{m}$ and $i + j + k + l + m = 2^{p}$

By the pumping lemma,

$w v^{2} x y^{2} z = a^{i} a^{2 j} a^{k} a^{2 l} a^{m}$

Because $i + j + k + l + m = 2^{p}$ and $j + l \geq 1$

Thus $j + l < i + j + k + l + m < i + 2 j + k + 2 l + m$

Therefore $i + 2 j + k + 2 l + m$ should at least be $2^{p + 1} = 2 (i + j + k + l + m)$

Which means $j + l = i + j + k + l + m$ which is a contradiction.

Therefore $w v^{2} x y^{2} z$ is not in L.

Therefore L is not context-free.

3. Convert the following grammar to an NPDA. (8pt)

E \to E + E | i d

4. Let $Σ = {a, b}$ . Design a (nondeterministic) TM for each following language. (10 pt each)

a. ${a^{n} b^{m} | m \geq n}$

4-a

b. ${w | w i s a p a l i n d r o m e}$

4-b

c. ${w | w i s n o t a p a l i n d r o m e}$

4-c

d. ${a^{n} | n = 2^{x} f o r x \in N}$

4-d

5. Design a TM for each integer subtraction: $a - b$ for $a, b \in N$ . You need to clearly how the input and the side effect are encoded. (8pt each)

Let $Γ = {0, #, -, x}$

Use 0 to represent positive numbers in the unary system.
Use # as a separator between the two numbers.
Use - as a special marker to indicate a negative result when $b > a$ .
Use x as a symbol to do the subtraction.

Input Format

The first part of the tape will consist of a sequence of 0s representing $a$ .
The second part, after the separator #, will contain a sequence of 10s representing $b$ .

For example:

000#00 represents $3 - 2$ , should be output as 0 (positive result).
00#000 represents $2 - 3$ , and should be output as -0 (negative result).

Algorithm

Tutorial

assignment

Assignment

As-1

As-2

Lab-1

Lab-2

Lab-3

Lab-4

GAMES101

Assignment-1

Assignment-2

Assignment-3

Assignment-4

Lab

Lecture

Peoject

CSCN

Cell Cell Communication

Ploidy

TOC-As-3

TOC-As-3 ​

1. Construct NPDA’s that recognize the following languages over Σ={a,b,c}. (10 pt for each) ​

a. L2={anbmcn+m|n,m≥0} ​

b. L3={anbn+mcm|n,m≥0} ​

c. L4={a3bncn|n≥0} ​

2. Show that the language {an|n=2xfor all x∈N} is not contexr-free. ​

3. Convert the following grammar to an NPDA. (8pt) ​

4. Let Σ={a,b}. Design a (nondeterministic) TM for each following language. (10 pt each) ​

a. {anbm|m≥n} ​

b. {w|w is a palindrome} ​

c. {w|w is not a palindrome} ​

d. {an|n=2xfor x∈N} ​

5. Design a TM for each integer subtraction: a−b for a,b∈N. You need to clearly how the input and the side effect are encoded. (8pt each) ​

6. Let Γ={a,b,⊔} Design a TM which decides whether the symbol b is on the tape. (8pt) ​

TOC-As-3

1. Construct NPDA’s that recognize the following languages over $Σ = {a, b, c}$ . (10 pt for each)

a. $L_{2} = {a^{n} b^{m} c^{n + m} | n, m \geq 0}$

b. $L_{3} = {a^{n} b^{n + m} c^{m} | n, m \geq 0}$

c. $L_{4} = {a^{3} b^{n} c^{n} | n \geq 0}$

2. Show that the language ${a^{n} | n = 2^{x} f o r a l l x \in N}$ is not contexr-free.

3. Convert the following grammar to an NPDA. (8pt)

4. Let $Σ = {a, b}$ . Design a (nondeterministic) TM for each following language. (10 pt each)

a. ${a^{n} b^{m} | m \geq n}$

b. ${w | w i s a p a l i n d r o m e}$

c. ${w | w i s n o t a p a l i n d r o m e}$

d. ${a^{n} | n = 2^{x} f o r x \in N}$

5. Design a TM for each integer subtraction: $a - b$ for $a, b \in N$ . You need to clearly how the input and the side effect are encoded. (8pt each)

6. Let $Γ = {a, b, ⊔}$ Design a $T M$ which decides whether the symbol $b$ is on the tape. (8pt)