Answers.Body: <p>The process of automatically learning a grammar from examples of a language is called <a href="https://en.wikipedia.org/wiki/Grammar_induction" rel="nofollow noreferrer">grammar induction</a>. Since you mention that <em>L</em> can be "augmented and changed", it might be feasible to solve this problem using an <a href="https://scholar.google.com/scholar?hl=en&amp;as_sdt=0%2C47&amp;q=%22adaptive+%28parser+OR+parsing%29%22&amp;btnG=" rel="nofollow noreferrer">adaptive parser</a>.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-03-27T19:22:58.567Z
Answers.Text: Has this been applied to NLP purposes, after POS tagging?
Answers.UserDisplayName: lee
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-03-29T22:24:33.267Z
Answers.Text: Grammar induction has also been [used in some machine-translation systems](https://www.google.com/search?q=%22grammar+induction%22+machine+translation),
Answers.UserDisplayName: Anderson Green
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-03-30T15:17:48.473Z
Answers.Text: Do you happen to have any idea how successful these methods were compared to the typical approaches?
Answers.UserDisplayName: lee
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-01-30T07:17:37.947Z
Answers.LastActivityDate: 2018-01-30T07:17:37.947Z
Answers.UserDisplayName: Anderson Green
Body: <p>Suppose I have context-free grammar (CFG) <span class="math-container">$L$</span> that pumps out words in that language. I want a machine learning system that can detect if a word <span class="math-container">$w$</span> came from <span class="math-container">$L$</span> or not. It has access to a stream from <span class="math-container">$L$</span> that is constantly producing words in <span class="math-container">$L$</span> at random. In this case, the system can only be trained with positive examples. The system also has access to a verifier for <span class="math-container">$L$</span>. The system (if it chooses to) can generate strings and verify that the string is in <span class="math-container">$L$</span> or not. However, the system could just cheat and just use the verifier, so during the test phase, it gets disabled (during the learning phase, it uses the verifier as much as it wants). Moreover, <span class="math-container">$L$</span> can be augmented and changed, and the system should adapt to that change.</p>
  
  <p>For instance, let's consider this regex (a regex is a CFG): <span class="math-container">$$(aa)*$$</span></p>
  
  <p>This language only produces a string of <span class="math-container">$aa$</span>'s of even length. Suppose I modified the regex to <span class="math-container">$(aa|bb)*$</span>. This system should adapt to recognize this new language.</p>
  
  <p>What kind of methods/approaches should I consider in my design?</p>
  
Tags: <machine-learning><natural-language-processing><ai-design><grammar-induction>
Title: How can I implement an AI system that learns to recognise a context-free grammar?
UserDisplayName: lee
ThreadText: # How can I implement an AI system that learns to recognise a context-free grammar?
  
  (Asked by: username_0 on 2017-10-04)
  
  Suppose I have context-free grammar (CFG) $L$ that pumps out words in that language. I want a machine learning system that can detect if a word $w$ came from $L$ or not. It has access to a stream from $L$ that is constantly producing words in $L$ at random. In this case, the system can only be trained with positive examples. The system also has access to a verifier for $L$. The system (if it chooses to) can generate strings and verify that the string is in $L$ or not. However, the system could just cheat and just use the verifier, so during the test phase, it gets disabled (during the learning phase, it uses the verifier as much as it wants). Moreover, $L$ can be augmented and changed, and the system should adapt to that change.
  
  For instance, let's consider this regex (a regex is a CFG): $$(aa)\*$$
  
  This language only produces a string of $aa$'s of even length. Suppose I modified the regex to $(aa|bb)\*$. This system should adapt to recognize this new language.
  
  What kind of methods/approaches should I consider in my design?
  
  **Tags:** machine-learning, natural-language-processing, ai-design, grammar-induction
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2018-01-30. Score: 3 | Accepted answer
  
  The process of automatically learning a grammar from examples of a language is called [grammar induction](https://en.wikipedia.org/wiki/Grammar_induction). Since you mention that *L* can be "augmented and changed", it might be feasible to solve this problem using an [adaptive parser](https://scholar.google.com/scholar?hl=en&as_sdt=0%2C47&q=%22adaptive+%28parser+OR+parsing%29%22&btnG=).
  
  > **Comments:**
  > **username_0**: Has this been applied to NLP purposes, after POS tagging?  
  > **username_1**: Grammar induction has also been [used in some machine-translation systems](https://www.google.com/search?q=%22grammar+induction%22+machine+translation),  
  > **username_0**: Do you happen to have any idea how successful these methods were compared to the typical approaches?  
  
  ---
  
  