CountingSort(A, B, k)
for i=1 to k
C[i]= 0;
for j=1 to n
C[A[j]] += 1;...
CountingSort(A, B, k)
for i=1 to k
C[i]= 0;
for j=1 to n
C[A[j]] += 1;
for i=2 to k
C[i] = C[i] + C[i-1];
for j=n downto 1
B[C[A[j]]] = A[j];
C[A[j]] -= 1;
illustrate the operation of COUNTING-SORT on the array A =
{6,0,2,0, 1, 3, 5, 6, 1, 3, 2}. Specifically, show the four arrays
A, B, C, and C'.
Question 2
a) Construct a Pushdown Automaton (PDA) for the language L (M) = {a, b}*...
Question 2
a) Construct a Pushdown Automaton (PDA) for the language L (M) = {a, b}* where, if there
are any a’s must precede all b's and the number of b's must be equal to or twice the number
of a’s.
a) Trace the computations for the strings aabb, bbb, and abb in the PDA obtained in Question 2
9. Let S = {a,b,c,d,e,f,g,h,i,j}.
a. is {{a}, {b, c}, {e, g}, {h, i, j}} a...
9. Let S = {a,b,c,d,e,f,g,h,i,j}.
a. is {{a}, {b, c}, {e, g}, {h, i, j}} a partition of S?
Explain.
b. is {{a, b}, {c, d}, {e, f}, {g, h}, {h, i, j}} a partition
of S? Explain. c. is {{a, b}, {c, d}, {e, f}, {g, h}, {i, j}} a
partition of S? Explain.
Use CFG or PDA to prove L=
{0a1b0c : b ≠ a + c; a, b,...
Use CFG or PDA to prove L=
{0a1b0c : b ≠ a + c; a, b, c ≥ _0}
is a context-free language. Please add your explanation, thank
you.
If you can use the theorem(union of CFL and regular language =
CFL) is also welcomed.