I am proposing a solution for problem 2..
>2.
> Given a text file, implement a solution to find out if a pattern
> similar to wild cards can be detected.
> fort example find if a*b*cd*, or *win or *def* exists in the text.
Whatever be the pattern sort it must be regular expression. So in
principle, there always exists a deterministic finite automata with
exactly one finite state to accept the pattern.
Thus, the problem can be solved. For example take the case for
a*b*cd*. The automaton can can written as:
1.Set state=1.
2. Scan the string until end of string is reached.
2.1. If state is 1 and the letter is a then do not change the
state.
If the state is 1 and the letter is b then go to state 2.
if the state is 1 and the letter is c then go to state 3.
if the state is 1 and the letter is d then go to state 4.
if the state is 2 and letter is a then go to state 4.
if the state is 2 and the letter is b then do not change
the state.
if the state is 2 and the letter is c the go to state 3.
if the state is 2 and the letter is d then go to state 4.
if the state is 3 and the letter is a,b or c then go to
state 4.
if the state is 3 and the letter is d then do not change
state.
if the state is 4 then do not change state.
3. If the state is 3 output "accept" else output "reject".
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
