Click here to Skip to main content
15,901,035 members
Please Sign up or sign in to vote.
1.00/5 (2 votes)
See more:
Suppose we allow the pattern P to contain occurrences of a gap character ◊ that can match an arbitrary string of characters (even one of zero length). For example, the pattern ab◊ba◊c occurs in the text cabccbacbacab
Note that the gap character may occur an arbitrary number of times in the pattern but not at all in the text. Give a polynomial-time algorithm to determine whether such a pattern P occurs in a given text T, and analyze the running time of your algorithm.

I have googled but didnt find an answer. I only need to understand psuedocode.
I do have some idea that the pattern can be first converted into a regular expression then an NFA can be made which then need to be converted to a DFA...but I am not sure if this is the right approach?
Posted
Updated 24-Apr-15 2:04am
v3

1 solution

"I do have some idea that the pattern can be first converted into a regular expression then an NFA can be made which then need to be converted to a DFA...but I am not sure if this is the right approach?"

No - that's not an algorithm, which is what your tutor is looking for.
He hasn't asked for an implementation, he's looking for the underlying way that the task needs to be done, and an analysis of how well it works.

And we aren't going to do that for you!
We do not do your homework: it is set for a reason. It is there so that you think about what you have been told, and try to understand it. It is also there so that your tutor can identify areas where you are weak, and focus more attention on remedial action.

Try it yourself, you may find it is not as difficult as you think.
 
Share this answer
 
Comments
Member 11578993 24-Apr-15 9:19am    
any hint please? I think I have to make a transition function.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900