consider a language of the following character strings The l

consider a language of the following character strings: The letter A; the letter B; the letter C followed by a string that is in the language; the letter D followed by a string in the language. For example, these strings are in this language: A, CA, CCA, DCA, B, CB, CCB, DB, DCCB.

a. Wtrite a grammar for this language.

b. Is CAB in this language? Explain.

c. Write a recursive recognition algorithm for this language.

Solution

1:Producing grammar for each sub-expression and then combining
a
+b

c ab+c abc+
Sa aSa | aBa | aCa
Ba bBa | cCa |
Ca cCa |
Sb aSb | bBb | bCb
Bb bBb | cCb |
Cb cCb |
Sc aSc | bBc | cCc
Bc bBc | cCc
Cc cCc |
S aS | aB | aC
S bB | bC
S cC
B bB | cC |
C cC |
Note that Ca, Cb and Cc are same and Ba, Bb and Bc are functionally same under the union

2:CAB : NO CAB WILL NOT COME IN THIS LANGUAGE BECAUSE :

the grammer is going and taking alphabates which are after the alphabate and in CAB AB comes after C so not possible in this language.

3:RECURSIVE RECOGNITION ALGORITHM FOR THIS LANGUAGE GRAMMER :

1 - Generate the natural numbers, one-at-a-time, N = 1, 2, 3, 4, 5, ...
2 - For each N, generate all the numbers W = 1, 2, 3, ..., N
3 - For a given W find the N-th word w_W in a canonical sequence for \\Sigma* (just count off the words up to the M-th word, e.g. the 15th word in the ordering we gave above for {a, b, c}* was aab)
4 - Run the procedure P on w_M for up to N - W steps. If the procedure accepts w_W within the N - W steps, check if w_W was already produced as an output. If not, output w_M . If w_W has already appeard in the output, or if procedure P did not accept w_M in N - W steps, then consider the number W:
5 - If W = N, go to step 1 and start over with N + 1 in place of N
6 - If W< N, replace W by N + 1 and start over at step 3.

This whole procedure (steps 1 through 6) will eventually output any string in the language recognized by P.