Talk:String operations

Computer science Start‑class Mid‑importance

This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science

Start

This article has been rated as Start-class on Wikipedia's content assessment scale.

Mid

This article has been rated as Mid-importance on the project's importance scale.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

Substitution: maps to languages or to strings or either?

Naive question: In "String substitution" we read that the a substitution "... is a mapping f that maps letters ... to languages"; but in "String homomorphism" we read that a homomorphism "... is a string substitution such that each letter is replaced by a single string". Now strings are categorically distinct from languages (aren't they?), so surely a substitution can't be defined both as something that maps letters to languages and also as something that maps letters to strings. It seems confusing at best. --Bmcm (talk) 12:22, 19 February 2014 (UTC)[reply]

I agree. Hopcroft and Ullman, after having defined substitutions and strings (on p.60) in the same way as in the article, add the following remark: "We generally take h(a) [for a homomorphism h] to be the string itself, rather than the set containing that string." A similar remark should be added in the article. - Jochen Burghardt (talk) 17:59, 19 February 2014 (UTC)[reply]

String substitution

What does this mean? An example of string substitution occurs in regular languages, which are closed under string substitution. That is, if the letters of a regular language are substituted by other regular languages, the result is still a regular language. What is the reference? Deltahedron (talk) 21:05, 22 March 2013 (UTC)[reply]

I'll think about an example for that. Meanwhile, I hope that the examples I added are helpful and not too trivial.

Another question: aren't regular (string) languages also closed w.r.t. inverse string homomorphisms? The TATA-Book (reference see Regular_tree_grammar#External_links) says, even regular tree languages are. However, I didn't check whether its notion of inverse homomorphism its similar to the one here. Jochen Burghardt (talk) 15:52, 25 May 2013 (UTC)[reply]

Prefix example question

(I came here to get an idea what 'prefix-closed assertion' could mean) The example says $L=\left\{abc\right\}{\mbox{ then }}\operatorname {Pref} (L)=\left\{\varepsilon ,a,ab,abc\right\}$
what I don't know: does that mean 'abc' is the only word, so I might shorten the word but not mix it/ make it longer? thanks