Strings and languages Terms for a part of string
| Term | Definition |
| Prefix of S | A string obtained by removing zero or more trailing symbol of string S. e.g., ban is prefix of banana. |
| Suffix of S | A string obtained by removing zero or more leading symbol of string S. e.g., nana is suffix of banana. |
| Sub string of S | A string obtained by removing prefix and suffix from S. e.g., nan is substring of banana. |
| Proper prefix, suffix and substring of S | Any nonempty string x that is respectively prefix, suffix or substring of S, such that s≠x |
| Subsequence of S | A string obtained by removing zero or more not necessarily contiguous symbol from S. e.g., baaa is subsequence of banana. |
Operation on languages Definition of operation on language
| Operation | Definition |
| Union of L and M Written L U M | L U M = {s | s is in L or s is in M } |
| concatenation of L and M Written LM | LM = {st | s is in L and t is in M } |
| Kleene closure of L written L* | L* denotes “zero or more concatenation of” L. |
| Positive closure of L written L+ | L+ denotes “one or more concatenation of” L. |