— the set of productions. The production is usually denoted asIn this problem and variables are denoted by capital letters of the English alphabet. An empty word is denoted as .Let β and γ be words over Ifwe say that β tranforms to γ and write In other words, if it is allowed to take β and replace any occurance of A with the word α ,We will sayif γ can be obtained from β with zero or more transformations. For example, let In this case since
The number of characters in a word α is called the length of this word and is denoted as |α|
Let k be an integer number. We say that a word is a valid k-pre x if one of the following is true:
Given a context free grammar and a number k find all valid k-prefixes.
2 3 S->0S1S S-> 1 3 S->SS 1 3 A->0
5 eps 000 001 01 010 0 0