The first step in parsing a language often involves matching an input string against a set...

Transcribed Image Text:

The first step in parsing a language often involves matching an input string against a set of a patterns. In this problem, we allow a pattern to be any sequence of alphabetic letters (e.g., 'a', 'b', ..., 'z') and the special character ? (which can be any single alphabetic character). For example, the pattern ab2d7t would match the inputs "abcdef", "abbddf", and "abzdzf", but it would not match "bbbbbb" or "abc". We call a set of patterns unambiguous if no input string can be matched by two or more patterns in the set. For example, the set of patterns (a, be, za) is unambiguous, but the set of patterns (a, be, ?e) is ambiguous because the patterns be and te both match the input string "bc". Given a set of patterns, briefly describe an efficient algorithm that determines whether the set is ambiguous. You may use one of the following data structures to help you: BST, AVL Tree, Trie, LLRB Tree. Your description should take 1-2 sentences. Be sure to also justify the efficiency of your answer by providing the worst case running time of your algorithm in O(-) notation. Use the variable n to represent the number of patterns in your set. The first step in parsing a language often involves matching an input string against a set of a patterns. In this problem, we allow a pattern to be any sequence of alphabetic letters (e.g., 'a', 'b', ..., 'z') and the special character ? (which can be any single alphabetic character). For example, the pattern ab2d7t would match the inputs "abcdef", "abbddf", and "abzdzf", but it would not match "bbbbbb" or "abc". We call a set of patterns unambiguous if no input string can be matched by two or more patterns in the set. For example, the set of patterns (a, be, za) is unambiguous, but the set of patterns (a, be, ?e) is ambiguous because the patterns be and te both match the input string "bc". Given a set of patterns, briefly describe an efficient algorithm that determines whether the set is ambiguous. You may use one of the following data structures to help you: BST, AVL Tree, Trie, LLRB Tree. Your description should take 1-2 sentences. Be sure to also justify the efficiency of your answer by providing the worst case running time of your algorithm in O(-) notation. Use the variable n to represent the number of patterns in your set.

Answer rating: 100% (QA)

Efficient algorithm for checking pattern ambiguity Data Structure Trie Description Insert each patte... View the full answer