Question

Consider the following Context Free Grammar G ((A, B, C), (a, $), P, S):

P:
S → AB | BC
A → BA |CCA| a
B → CC |$
C → AB | a
Using CYK algorithm find out whether the string a$a$ is a member of the language L(G) or not?
b) Consider the following Context Free Grammar G ((A, B, C), (x, -), P, S):
P:
S → AB | BC
A → BA | x
B → CC |ABC| -
C → AB | x
String x-x-x is a member of the language L(G). Is the statement True or False? Justify your answer with the help of CYK algorithm.

Answer 1

Explanation:

Here is the step-by-step process:

Step 1: Constructing the parse table

The parse table is a 2D table where each cell represents a non-terminal symbol that derives the corresponding substring of the input string.

We have the following CFG:

P:

S → AB | BC

A → BA | CCA | a

B → CC | $

C → AB | a

The input string is "a$a$".

Start by dividing the string into individual characters and initialize the parse table:

| 1 | 2 | 3 | 4 |

------------------------------

1 | | | | |

------------------------------

2 | | | | |

------------------------------

3 | | | | |

------------------------------

4 | | | | |

Step 2: Filling the diagonal cells

Fill the diagonal cells of the parse table based on the terminal symbols in the input string.

For the given input "a$a$", the diagonal cells will be filled as follows:

| 1 | 2 | 3 | 4 |

------------------------------

1 | a | | | |

------------------------------

2 | | $ | | |

------------------------------

3 | | | a | |

------------------------------

4 | | | | $ |

Step 3: Filling the remaining cells

Fill the remaining cells of the parse table based on the production rules of the CFG.

Using the given CFG, we can fill the cells as follows:

| 1 | 2 | 3 | 4 |

------------------------------

1 | a | | A | S |

------------------------------

2 | | $ | C | B |

------------------------------

3 | B | | a | C |

------------------------------

4 | C | | B | $ |

Step 4: Checking membership

To determine if the string "a$a$" is a member of the language L(G), we check if the start symbol S appears in the top-right cell of the parse table.

In this case, the start symbol S appears in the top-right cell of the parse table, which means that the string "a$a$" can be derived from the given CFG.

Therefore, the string "a$a$" is a member of the language generated by the CFG.