计算机有可能“学习"计算机吗?用户提供的示例的正则表达式? [英] Is it possible for a computer to "learn" a regular expression by user-provided examples?

问题描述

计算机是否可以通过用户提供的示例学习"正则表达式?

Is it possible for a computer to "learn" a regular expression by user-provided examples?

要澄清:

• 我不不想学习正则表达式.
• 我想创建一个程序，该程序从用户交互提供的示例中学习"正则表达式，也许可以通过从文本中选择部分或选择开始或结束标记来实现.

• I do not want to learn regular expressions.
• I want to create a program which "learns" a regular expression from examples which are interactively provided by a user, perhaps by selecting parts from a text or selecting begin or end markers.

有可能吗?我可以使用Google提供的算法，关键字等吗?

Is it possible? Are there algorithms, keywords, etc. which I can Google for?

编辑:谢谢您的回答，但是我对提供此功能的工具不感兴趣.我正在寻找理论信息，例如论文，教程，源代码，算法名称，以便为自己创建一些东西.

EDIT: Thank you for the answers, but I'm not interested in tools which provide this feature. I'm looking for theoretical information, like papers, tutorials, source code, names of algorithms, so I can create something for myself.

推荐答案

这本书 《计算学习理论简介》 包含用于学习有限自动机的算法.由于每种常规语言都等效于有限的自动机，因此可以通过程序学习某些正则表达式. 知识和英勇显示一些不可能学习有限自动机的情况.一个相关的问题是学习隐马尔可夫模型，这是一种概率自动机，可以描述一个字符序列.请注意，编程语言中使用的大多数现代正则表达式"实际上比常规语言要强大，因此有时更难学习.

The book An Introduction to Computational Learning Theory contains an algorithm for learning a finite automaton. As every regular language is equivalent to a finite automaton, it is possible to learn some regular expressions by a program. Kearns and Valiant show some cases where it is not possible to learn a finite automaton. A related problem is learning hidden Markov Models, which are probabilistic automata that can describe a character sequence. Note that most modern "regular expressions" used in programming languages are actually stronger than regular languages, and therefore sometimes harder to learn.

这篇关于计算机有可能“学习"计算机吗?用户提供的示例的正则表达式?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！