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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.