Talk:String operations

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)

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)

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)

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)

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

Right Quotient

The article says:

The right quotient of a character a from a string s is the truncation of the character a in the string s, from the right hand side. It is denoted as $s/a$. If the string does not have a on the right hand side, the result is the empty string.

This is followed by the following comment, which is only visible in the HTML source:

This definition deviates from Hopcroft.Ullman.1979, as remarked below. I guess the former doesn't have widespread use, if it has a source at all.

I know a bit about the history of formal language theory, and was able to track the notion of the quotient of formal languages, as defined in the Hopcroft/Ullman 1979 book, back to a paper by Ginsburg and Spanier (J. ACM, 1693). They state that the notion of quotients (of languages, not of strings) was investigated by the "SHARE Theory of Information Handling Committee" at the time. I would suggest to keep the Hopcroft/Ullman definition of quotients (of languages) and remove the deviating, unsourced definition of quotient (of strings, then extended to quotients of languages). Hermel (talk) 20:36, 15 April 2018 (UTC)

Probably, the HTML comment was inserted by me, when I tried to obtain sources for all the definitions. I agree with your suggestion. In addition, we should add your JACM 1963 reference (I understood that Ginsburg and Spanier gave the same definition as Hopcroft.Ullman.1979, right?). Via ACM and Researchgate, I found this bib.data:

• Seymour Ginsburg and Edwin H. Spanier (Oct 1963). "Quotients of Context-Free Languages". Journal of the ACM. 10 (4): 487–492. — ABSTRACT: The following results on the quotient of context-free languages (CFL) are shown: (1) It is recursively unsolvable to determine for arbitrary CFL whether the quotient of one by another is a CFL. (2) If either set is regular and the other is a CFL, then the quotient is a CFL.

Maybe you can help to resolve some of the remaining [citation needed], too? - Jochen Burghardt (talk) 08:46, 16 April 2018 (UTC)

The example of substitution using ß ~ SS is not entirely correct

As noted on ß, there is an uppercase form of the letter ß, namely ẞ. There is nothing theoretically wrong with the example, but the wording "no uppercase char available" might be rephrased to reflect this fact. (It's funny how using examples from ordinary languages often backfires.) Lasse Hillerøe Petersen (talk) 09:15, 3 June 2023 (UTC)