Question

c) Determine the language, L, that is recognized by this PDA. q8 q7 c,b:A

Answer 1

Let x,y and z denote the count of a,b and c respectively in the language.

So, strings accepted by the PDA are in the form a^xb^yc^z

There are some conditions on x, y and z.

There should at least 1 a. (q1->q2). So, x>=1

There should at least 1 b. (q2->q3). So, y>=1

Now, We have 3 cases,

1. Transitions from q3->q7->q8.

No. of b= No. of a

So, We should have at least 1 c.

2. Transitions from q3->q4->q5->q6.

No. of b> No. of a

So, No. of c's should be greater than extra b's. So, z> (y-x)

3. Transitions from q3->q9->q10.

No. of a> No. of b

So, No. of c's should be greater than or equal to extra a's. So, z>= (x-y)

So, We can categorize 3 cases in a single statement

z>= max(x-y, y-x+1)

So,

L = {(a,b,c)^*| a^xb^yc^z such tha x>=1 and y>=1 and z>=max(x-y,y-x+1)}