Detecting patterns in finite regular and context-free languages |
| |
Authors: | Narad Rampersad Jeffrey Shallit |
| |
Affiliation: | a Department of Mathematics and Statistics, University of Winnipeg, 515 Portage Ave., Winnipeg, MB R3B 2E9, Canada b School of Computer Science, University of Waterloo, Waterloo, ON N2L 3G1, Canada |
| |
Abstract: | We consider some natural variations on the following classic pattern-matching problem: given an NFA M over the alphabet Σ and a pattern p over some alphabet Δ, does there exist a word x∈L(M) such that x matches p? We consider the restricted problem where M only accepts a finite language. We also consider the variation where only some factor of x is required to match the pattern p. We show that both of these problems are NP-complete. We also consider the same problems for context-free grammars; in this case the problems become PSPACE-complete. |
| |
Keywords: | Formal languages Pattern matching Finite automaton Regular language Context-free language |
本文献已被 ScienceDirect 等数据库收录! |
|