The Gateway to Computer Science Excellence
0 votes
In some applications, such as programs that check spelling, we may not need an exact match of
the pattern, only an approximate one. Once the notion of an approximate match has been made
precise, automata theory can be applied to construct approximate pattern matchers. As an
illustration of this, consider patterns derived from the original ones by insertion of one symbol.
Let L be a regular language on $Σ$ and define
        $insert (L) =$ {$uav : a ∈ Σ,uv ∈ L$}.
In effect, $insert (L)$ contains all the words created from $L$ by inserting a spurious symbol
anywhere in a word.
(a) Given an nfa for $L$, show how one can construct an nfa for $insert (L)$.
(b) Discuss how you might use this to write a pattern-recognition program for $insert (L)$, using as
input a regular expression for $L$.
in Theory of Computation by Boss (15.4k points) | 6 views

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,397 answers
105,456 users