This is the
talk page for discussing improvements to the
Regular language article. This is not a forum for general discussion of the article's subject. |
Article policies
|
Find sources: Google ( books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
This article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
I removed the following:
I think one could argue that context-free languages are also built according to limited syntax rules. I'm pretty sure the word "regular" was chosen without much thinking; it's one of those meaningless terms, like "normal", that are used all over the place. Also, the above "these expressions" seems to refer to regular expressions, but regular expressions hadn't been mentioned in the article at that point. --AxelBoldt
A regular language is a formal language (i.e. a possibly infinite set of finite sequences of symbols from a finite alphabet) that has one of the following equivalent properties:
Modern "regular" expressions can describe more languages than just regular ones. Example: /([a-z]*)\\1/ (weird software problem - there should be 1 backslash there) -- Taw
I'm reading about regular languages for the first time, so am curious about few things which I could not find in the article.
Jay 07:48, 14 Nov 2003 (UTC)
References
{{
cite journal}}
: Cite has empty unknown parameter: |month=
(
help)
'# it can be accepted by a deterministic finite state machine.' is superfluous. Every NFA has an equivalent DFA. So by requiring a regular language to be accepted by an NFA requires it to be accepted by a (the corrisponding DFA)
This article describes the properties of regular languages and gives a few examples, but I think a kind of formal definition was missing. I added a well-known recursive definition. I think it fits pretty well in the article. What do you think? -- Alexandre 22:27, 25 Jun 2004 (UTC)
The formal definition needs to include {ε} as an atomic language.
Tobinyehle ( talk) 16:56, 22 February 2016 (UTC)
The recursive definition is quite nice. There's something I don't understand here, though. Why is the kleene star required in the recursive definition? It seems to me that you can construct it by induction using concatenation.
Here's a proof. Is it incorrect somewhere?
Suppose L is regular. If is regular, then concatenate to get that is regular. Union with . Therefore L* is regular.
Can anybody talk about properties of non - regular languages? (unsigned, undated)
it would be of great help if some one could post more info about non regular languages 7 OCT 2007 —Preceding
unsigned comment added by
64.234.33.191 (
talk)
19:18, 7 October 2007 (UTC)
The article states that regular languages are closed under the "half", "log" and "sqrt" operations. What are these? I could guess that , but that is not the inverse of the square of a language. I have no idea for the other two. Eric119 19:31, 14 August 2006 (UTC)
Regular languages most definitely are closed under this operation. The proof is a little long and I am not including it here. It can be found in the text of Problem Solving in Automata, Languages, and Complexity by Ding-Zhu Du and Ker-I Ko. The basic idea however is that if L is regular, then a DFA exists that accepts it. We want to make a new machine that has this original machine and also a copy of it that runs backwards (non-deterministically). We want to run these in parallel on input. If the parallel machines stops with both machines in the same state (note that this state is not necessarily in the set of final states of the original machine) then we have half of L Isometric 05:40, 17 October 2006 (UTC)
Regular language is closed under HALF. If A is a regular language, then HALF(A) = {x|xy in A and |x|=|y|}. The proof is like this: Given DFA D that recognizes A, you can guess that, given a string w in A, after running through the first half of w, you will end up in some state q in D. So you make another machine M with initial state q, and make every transition in A to be a transition with 0,1, assume alphabet {0,1}. M has the same set of accept states as A. Now you can run D and A in parallel, this can be done with subset construction. You accept x if running x on A ends up in state q, and running {0,1}* for |x| steps on M ends in an accept state. You repeat this for every state q of D and accept x if one of them both have D end up in state q and M start from q and end up in an accept state.
This proof works in general, that is, any constant fraction of a regular language is also regular. E.g. if A is regular, then the first third, or the middle third, or the last third, all three languages are regular.
Reference: Sterns and Hartmanis, Regularity Preserving Modifications of Regular Expressions, Information and Control, v6, 1963, pp 55-69
BTW, the paper is available in many university libraries; But googling it brings up the following link
Admittedly, it is behind a WP:PAYWALL, but still... Hermel ( talk) 19:58, 11 March 2011 (UTC)
The Article first describes regular language as one that is accepted by a deterministic finite state machine. Then it defines it using the recursive definition. The point is that either one can be used as definition. However, if one is used as definition, the other one must be proved as theorem.-- CBKAtTopsails 16:20, 6 June 2007 (UTC)
Um... I'm not exactly an expert on the subject, but doesn't it certainly not contain AC0? I'm hesitant to take it out, because I don't really know what I'm talking about (not to mention that I don't want to say they're separate without a source, and just cutting it might imply to the casual reader that it does contain it), but it seems to me as though certain languages in AC0 being regular would allow you to use their DFAs to construct DFAs for L-hard languages, violating the space hierarchy theorem. Twin Bird ( talk) 04:40, 1 July 2011 (UTC)
I propose that Rational language (currently orphaned) be merged into Regular language. I think that the content in the rational language article can easily be explained in the context of regular languages, and this article is of a reasonable size that the merging of Rational language will not cause any problems as far as article size or undue weight is concerned. Hermel ( talk) 22:01, 3 August 2013 (UTC)
Actually, I'm unable to verify the [more general] def given on the Rational language from either of the sources cited! Both simply use "Rational language" as a 100% synonym for Regular language as far as I can tell. (See Talk:Rational language for specifics.) So simply redirecting that page here (and perhaps mentioning the synonym) is the best solution because there's nothing (verifiable) worth merging anywhere in that stub unless I've missed something in the tomes cited as refs there. JMP EAX ( talk) 00:08, 18 August 2014 (UTC)
Done. JMP EAX ( talk) 00:22, 19 August 2014 (UTC)
"the number of equivalence classes of its syntactic congruence is finite.[note 8][note 9] (This number equals the number of states of the minimal deterministic finite automaton accepting L.)"
I'm quite sure that the sentence in parentheses is not true. The number of equivalence classes of the syntactic congruence is the size of the syntactic monoid. This is also the size of the transition monoid of the minimal deterministic finite automaton accepting L. However, there are usually more elements in the monoid than states in the automaton. — Preceding unsigned comment added by 81.218.76.25 ( talk) 08:45, 6 October 2019 (UTC)
Indeed, for (ab+ba)* the minimum automaton has 4 states but the syntactic monoid has 15 elements. (The congruences are generated by aba ≡ a, bab ≡ b, abba ≡ baab and aaa ≡ bbb ≡ aaaa ≡ bbbb.) I think we should split the equivalent formalism into:
"the number of equivalence classes of its syntactic congruence is finite.[note 8][note 9]
"the number of equivalence classes of its left syntactic equivalence (also known as the right syntactic congruence.) is finite.[note 8][note 9] (This number equals the number of states of the minimal deterministic finite automaton accepting L.)"
The notes will need corresponding review. -- RichardW57m ( talk) 14:33, 1 April 2022 (UTC)
We also have regular and rational languages in the domain of trace languages. They are defined using different definitions that coincide for the free monoid of strings in an alphabet, namely recognition by DFAs and the purely algebraic definitions respectively, for not all rational trace languages are regular trace languages. The bad boy example is (U+0F73 TIBETAN VOWEL SIGN II}* in the domain of Unicode strings under canonical equivalence, with decomposable characters treated as syntactic sugar.
Should we mention such divergences here, or just have a headnote redirecting the read to Trace monoid for the use of the terms with respect to trace languages? That article doesn't yet have a section on these languages. -- RichardW57m ( talk) 12:02, 30 March 2022 (UTC)
This article was the subject of a Wiki Education Foundation-supported course assignment, between 21 August 2023 and 11 December 2023. Further details are available on the course page. Student editor(s): Sseligman26 ( article contribs).
— Assignment last updated by Fedfed2 ( talk) 00:53, 9 December 2023 (UTC)
This is the
talk page for discussing improvements to the
Regular language article. This is not a forum for general discussion of the article's subject. |
Article policies
|
Find sources: Google ( books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
This article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
I removed the following:
I think one could argue that context-free languages are also built according to limited syntax rules. I'm pretty sure the word "regular" was chosen without much thinking; it's one of those meaningless terms, like "normal", that are used all over the place. Also, the above "these expressions" seems to refer to regular expressions, but regular expressions hadn't been mentioned in the article at that point. --AxelBoldt
A regular language is a formal language (i.e. a possibly infinite set of finite sequences of symbols from a finite alphabet) that has one of the following equivalent properties:
Modern "regular" expressions can describe more languages than just regular ones. Example: /([a-z]*)\\1/ (weird software problem - there should be 1 backslash there) -- Taw
I'm reading about regular languages for the first time, so am curious about few things which I could not find in the article.
Jay 07:48, 14 Nov 2003 (UTC)
References
{{
cite journal}}
: Cite has empty unknown parameter: |month=
(
help)
'# it can be accepted by a deterministic finite state machine.' is superfluous. Every NFA has an equivalent DFA. So by requiring a regular language to be accepted by an NFA requires it to be accepted by a (the corrisponding DFA)
This article describes the properties of regular languages and gives a few examples, but I think a kind of formal definition was missing. I added a well-known recursive definition. I think it fits pretty well in the article. What do you think? -- Alexandre 22:27, 25 Jun 2004 (UTC)
The formal definition needs to include {ε} as an atomic language.
Tobinyehle ( talk) 16:56, 22 February 2016 (UTC)
The recursive definition is quite nice. There's something I don't understand here, though. Why is the kleene star required in the recursive definition? It seems to me that you can construct it by induction using concatenation.
Here's a proof. Is it incorrect somewhere?
Suppose L is regular. If is regular, then concatenate to get that is regular. Union with . Therefore L* is regular.
Can anybody talk about properties of non - regular languages? (unsigned, undated)
it would be of great help if some one could post more info about non regular languages 7 OCT 2007 —Preceding
unsigned comment added by
64.234.33.191 (
talk)
19:18, 7 October 2007 (UTC)
The article states that regular languages are closed under the "half", "log" and "sqrt" operations. What are these? I could guess that , but that is not the inverse of the square of a language. I have no idea for the other two. Eric119 19:31, 14 August 2006 (UTC)
Regular languages most definitely are closed under this operation. The proof is a little long and I am not including it here. It can be found in the text of Problem Solving in Automata, Languages, and Complexity by Ding-Zhu Du and Ker-I Ko. The basic idea however is that if L is regular, then a DFA exists that accepts it. We want to make a new machine that has this original machine and also a copy of it that runs backwards (non-deterministically). We want to run these in parallel on input. If the parallel machines stops with both machines in the same state (note that this state is not necessarily in the set of final states of the original machine) then we have half of L Isometric 05:40, 17 October 2006 (UTC)
Regular language is closed under HALF. If A is a regular language, then HALF(A) = {x|xy in A and |x|=|y|}. The proof is like this: Given DFA D that recognizes A, you can guess that, given a string w in A, after running through the first half of w, you will end up in some state q in D. So you make another machine M with initial state q, and make every transition in A to be a transition with 0,1, assume alphabet {0,1}. M has the same set of accept states as A. Now you can run D and A in parallel, this can be done with subset construction. You accept x if running x on A ends up in state q, and running {0,1}* for |x| steps on M ends in an accept state. You repeat this for every state q of D and accept x if one of them both have D end up in state q and M start from q and end up in an accept state.
This proof works in general, that is, any constant fraction of a regular language is also regular. E.g. if A is regular, then the first third, or the middle third, or the last third, all three languages are regular.
Reference: Sterns and Hartmanis, Regularity Preserving Modifications of Regular Expressions, Information and Control, v6, 1963, pp 55-69
BTW, the paper is available in many university libraries; But googling it brings up the following link
Admittedly, it is behind a WP:PAYWALL, but still... Hermel ( talk) 19:58, 11 March 2011 (UTC)
The Article first describes regular language as one that is accepted by a deterministic finite state machine. Then it defines it using the recursive definition. The point is that either one can be used as definition. However, if one is used as definition, the other one must be proved as theorem.-- CBKAtTopsails 16:20, 6 June 2007 (UTC)
Um... I'm not exactly an expert on the subject, but doesn't it certainly not contain AC0? I'm hesitant to take it out, because I don't really know what I'm talking about (not to mention that I don't want to say they're separate without a source, and just cutting it might imply to the casual reader that it does contain it), but it seems to me as though certain languages in AC0 being regular would allow you to use their DFAs to construct DFAs for L-hard languages, violating the space hierarchy theorem. Twin Bird ( talk) 04:40, 1 July 2011 (UTC)
I propose that Rational language (currently orphaned) be merged into Regular language. I think that the content in the rational language article can easily be explained in the context of regular languages, and this article is of a reasonable size that the merging of Rational language will not cause any problems as far as article size or undue weight is concerned. Hermel ( talk) 22:01, 3 August 2013 (UTC)
Actually, I'm unable to verify the [more general] def given on the Rational language from either of the sources cited! Both simply use "Rational language" as a 100% synonym for Regular language as far as I can tell. (See Talk:Rational language for specifics.) So simply redirecting that page here (and perhaps mentioning the synonym) is the best solution because there's nothing (verifiable) worth merging anywhere in that stub unless I've missed something in the tomes cited as refs there. JMP EAX ( talk) 00:08, 18 August 2014 (UTC)
Done. JMP EAX ( talk) 00:22, 19 August 2014 (UTC)
"the number of equivalence classes of its syntactic congruence is finite.[note 8][note 9] (This number equals the number of states of the minimal deterministic finite automaton accepting L.)"
I'm quite sure that the sentence in parentheses is not true. The number of equivalence classes of the syntactic congruence is the size of the syntactic monoid. This is also the size of the transition monoid of the minimal deterministic finite automaton accepting L. However, there are usually more elements in the monoid than states in the automaton. — Preceding unsigned comment added by 81.218.76.25 ( talk) 08:45, 6 October 2019 (UTC)
Indeed, for (ab+ba)* the minimum automaton has 4 states but the syntactic monoid has 15 elements. (The congruences are generated by aba ≡ a, bab ≡ b, abba ≡ baab and aaa ≡ bbb ≡ aaaa ≡ bbbb.) I think we should split the equivalent formalism into:
"the number of equivalence classes of its syntactic congruence is finite.[note 8][note 9]
"the number of equivalence classes of its left syntactic equivalence (also known as the right syntactic congruence.) is finite.[note 8][note 9] (This number equals the number of states of the minimal deterministic finite automaton accepting L.)"
The notes will need corresponding review. -- RichardW57m ( talk) 14:33, 1 April 2022 (UTC)
We also have regular and rational languages in the domain of trace languages. They are defined using different definitions that coincide for the free monoid of strings in an alphabet, namely recognition by DFAs and the purely algebraic definitions respectively, for not all rational trace languages are regular trace languages. The bad boy example is (U+0F73 TIBETAN VOWEL SIGN II}* in the domain of Unicode strings under canonical equivalence, with decomposable characters treated as syntactic sugar.
Should we mention such divergences here, or just have a headnote redirecting the read to Trace monoid for the use of the terms with respect to trace languages? That article doesn't yet have a section on these languages. -- RichardW57m ( talk) 12:02, 30 March 2022 (UTC)
This article was the subject of a Wiki Education Foundation-supported course assignment, between 21 August 2023 and 11 December 2023. Further details are available on the course page. Student editor(s): Sseligman26 ( article contribs).
— Assignment last updated by Fedfed2 ( talk) 00:53, 9 December 2023 (UTC)