Deadline: 2022-03-15 24:00

• The breadth first search is suitable for deriving a word in a context-free grammar.
  1. Consider the CF grammar \(G=(V,\Sigma,R,S)\), and construct the directed graph \(\vec{G}=((V\cup\Sigma)^*,\vec{E})\) where the vertices are the strings of terminal and non-terminal symbols. This graph has countably infinite number of vertices, but it is enough to search in a finite part of it for finding a derivation of a word.
  2. The graph \(\vec{G}\) contains the edge \((\alpha, \beta)\) if and only if there is a left-derivation step from the string \(\alpha \in (V \cup \Sigma)^*\) to the string \(\beta \in (V \cup \Sigma)^*\), in other words we get \(\beta\) if we apply a substitution rule from \(R\) on the first non-terminal symbol of \(\alpha\). Formally \begin{equation*} (\alpha, \beta) \in \vec{E} \Longleftrightarrow \exists w \in \Sigma^* \; \exists \gamma, \delta \in (V \cup \Sigma)^* \; \exists A \in V \colon (A \rightarrow \delta) \in R, \alpha = wA\gamma \textrm{ and } \beta = w\delta\gamma. \end{equation*}
  3. In this graph the left derivations of the word \(w \in L(G)\) are exactly the \(S \leadsto w\) paths, where \(S \in V\) is the start variable. All edges of a path correspond to a rule applied on the leftmost non-terminal symbol. We want to find such a path in this task.
• We give the skeleton of the program in the file cf_en.py. The only command line argument of this program is a word to derive. The program prints out the derivation to the standard output.

  The separation of the terminal and non terminal symbols is solved by a simple method: all capital letters A to Z of the English alphabet are possible non-terminal symbols while all other characters are terminal.

  1. The CF grammar is represented by the class Grammar. The start symbol is given to the constructor argument start_variable. Complete the add_rule method such that it adds the left and right side of a rule to the language. If necessary, modify the __init__ constructor creating a suitable data structure to store the rules.
  2. The derive method gets a word as a parameter and returns a left derivation in a list. If there is surely no such derivation, it returns False. To do this, it uses the breadth first search (presented in the previous task) algorithm realized by the private function _bfs_search. Because the graph is now infinite, we can not list all edges. Instead, we use the _next method producing a list of vertices that can be reached on an edge from the string vertex in the graph.

     Complete the _next method such that it returns a list of words which are available from the received string vertex by a single left derivation rule. For example, if the grammar is \begin{equation*} S \to aSB \mid bSA \mid \epsilon, \quad A \to aA \mid \epsilon, \quad B \to bB \mid \epsilon, \end{equation*} then

     self._next('aSbbB') == ['aaSBbbB', 'abSAbbB', 'abbB']
     	

  3. Let's try the program and find derivation to some given words. Please, answer the following questions in a """-type comment at the end of the code! (1) What language is specified in the file cf_en.py? (2) What happens when we give a word to the program that is not in the language? (3) A non mandatory question and task: how could we change the program code to handle this case? Do it!
• The isinstance() function and islower(), extend(), append() methods might help.