Given a grammar (in grammar.txt file) and a list of words (in words.txt file), the program will decide whether the given words are in the language defined by the grammar.
- Bitcoin: 1FHFU14DRWWHaJyq8fK1coKR57KqQJg2ZH
A sample grammar.txt file is given below. First line states the terminals (alphabet) of the language. Second line gives the Non-terminals of the grammar. Note that first non-terminal is the start symbol. After these initial two lines, rules of the grammars are given (one rule on each line). Each line starts with the ID of the rule (an integer). Every term in the grammar file is separated by a single space character. For simplicity, all the terminals and non-terminals are just a single character.
) ( + 0 1 *
S E
1 S -> ( E )
2 S -> E + E
3 S -> E * E
4 E -> S
5 E -> 0
6 E -> 1
The words.txt file will contain words (one word on each line). An example words.txt file is given below.
(0+1)+1
(1+11)
0*(1)
For each word in the words.txt file, if the word cannot be generated by the grammar, it will only print NO. If the word is in the language, it will print YES in the first line and on the next line it will print the rules which are applied to generate the word with a left-most derivation. The results are printed to results.txt file. For the grammar and words file given in the previous section, the results.txt file will be as follows:
YES
2 4 1 4 2 5 6 6
NO
YES
3 5 4 1 6