StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
6789130
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
0
CommunityOwnedDate
CreationDate
2011-07-22T11:12:34.520
FavoriteCount
0
LastActivityDate
2018-07-04T06:01:32.337
LastEditDate
2018-07-04T06:01:32.337
LastEditorUserId
8242447
OwnerUserId
2296705
ParentId
0
PostTypeId
5
Score
0
ViewCount
0
LastEditorDisplayName
text
Body
Given an alphabet (finite set of symbols) Σ, a language is a set of all sequences of such symbols in that alphabet. A language is a regular language exactly when it can be expressed in terms of a (formal) regular expression and the membership of any string can be decided by a finite-state machine. Regular languages belong to the highest hierarchy of the Chomsky Hierarchy, and are also called Type-3 grammars. They are above the Type-2 context-free languages which are recognized by pushdown automata, which are above the Type-1 context-sensitive languages recognized by linear bounded automata, and above the Type-0 recursively enumerable languages which can be recognized by Turing Machines. All regular languages are context-free, context-sensitive, and recursively enumerable. Formal regular expressions can be converted to deterministic finite state machines and to non deterministic finite machines and still represent the same regular language. Please do not confuse this with regex. Most regex engines are far more expressive than formal regular expressions, finite state machines, and can represent non-regular languages. <h2>Construction of a Regular Language</h2> The set of all regular languages over a given alphabet Σ can be produced exactly by this process: <ul> <li>The empty language <code>{}</code>, rejecting all strings.</li> <li>The language containing only the empty string <code>ε</code></li> <li>All languages containing only a single symbol <code>s ∈ Σ</code>.</li> <li>Every language created by the union, concatenation, or kleene-star of regular languages. Suppose <code>v</code> and <code>w</code> are strings of a regular language <code>A</code> and <code>B</code> respectively: <ul> <li>The union <code>(v|w)</code> is also regular. It accepts languages that are in any of <code>A</code> or <code>B</code>.</li> <li>The concatenation <code>vw</code> is also regular.</li> <li>The kleene-star <code>v*</code> is also regular. It means any copies of strings in <code>A</code> concatenated, including 0.</li> </ul></li> </ul> <h2>Examples and Nonexamples of Regular Languages</h2> <ul> <li>Given a simple alphabet <code>Σ = {0, 1}</code>, where <code>|</code> represents union, <code>*</code> represents kleene-star, these formal regular expressions all represent represents a regular language: <ul> <li>The regular expression <code>"0"</code>, <code>"1"</code>, <code>"(0|1)"</code>, <code>"01"</code>, <code>"11"</code>, <code>"0*"</code> are all regular.</li> <li>The regular expression <code>"(0(0|1)*1)"</code>, representing all binary strings beginning with 0 and ending with 1, is regular.</li> <li>Given a regular expression <code>R</code>, the language <code>"R+"</code> and <code>"R?"</code> all represent a regular language, whereas <code>+</code> represents one or more, and <code>?</code> represents zero or one. Namely, <code>"R+"</code> is equivalent to <code>"RR*"</code>, and <code>"R?"</code> is equivalent to <code>"(R|ε)"</code>.</li> <li>Given a regular expression <code>R</code>, the language <code>"R{m,n}"</code> is regular for all natural <code>m,n</code>, where <code>{m,n}</code> represents "from <code>m</code> copies to <code>n</code> copies". This is because it also involves union and concatenation: <code>"R{1,3}"</code> is expanded to <code>"(R|RR|RRR)"</code>.</li> </ul></li> <li>Given an alphabet used by regex engines, usually an ASCII or Unicode alphabet containing all ASCII or Unicode characters respectively: <ul> <li>The regex <code>/^.+$/</code> is regular. It includes all non-empty sequences of any character.</li> <li>The regex <code>/^#[A-Za-z]{1,3}[0-9]{2,4}$/</code> represents a regular language, consisting all strings which being with a hashtag, then one to three ASCII letters, followed by two to four decimal digits.</li> <li>The regex <code>/^([\d][\w])*$/</code> represents a regular language. It consists all strings which alternate digit characters and word characters. The shorthand <code>\d</code> and <code>\w</code> are examples of union.</li> </ul></li> <li>Many regex engines are much more expressive than regular languages. Backreferences can cause a regex to represent a non-regular language, and consequently they cannot be decided by a finite state machine. <ul> <li>The regex <code>"(.+)\1"</code> represents an irregular language. Involving a backreference capturing the first group <code>.+</code>, it accepts all the sequences of uppercase Latin letters repeated exactly twice. They are called squares in formal language theory. <ul> <li><code>"ABCABC"</code>, <code>"1234.1234."</code> are accepted</li> <li><code>"ABCAB"</code>, <code>"1234567891234567890"</code> are rejected.</li> </ul></li> </ul></li> </ul> <h2>Further Reading</h2> <ul> <li><a href="/questions/tagged/regex" class="post-tag" title="show questions tagged 'regex'" rel="tag">regex</a>: Short for regular expression. Many regex engines nowadays are far more expressive than formal regular expressions and finite-state machines.</li> <li><a href="/questions/tagged/finite-state-machine" class="post-tag" title="show questions tagged 'finite-state-machine'" rel="tag">finite-state-machine</a>: They are equivalent in expressiveness to formal regular expressions. They represent exactly the regular languages. Acronyms include FSM.</li> <li><a href="/questions/tagged/dfa" class="post-tag" title="show questions tagged 'dfa'" rel="tag">dfa</a>: Deterministic finite automaton. <a href="/questions/tagged/nfa" class="post-tag" title="show questions tagged 'nfa'" rel="tag">nfa</a> Nondeterministic finite automaton. <ul> <li>Both are equivalent in expressiveness.</li> </ul></li> <li><a href="/questions/tagged/context-free-grammar" class="post-tag" title="show questions tagged 'context-free-grammar'" rel="tag">context-free-grammar</a>, <a href="/questions/tagged/context-sensitive-grammar" class="post-tag" title="show questions tagged 'context-sensitive-grammar'" rel="tag">context-sensitive-grammar</a>: Tags referring to lower levels of the Chomsky hierarchy</li> <li><a href="http://en.wikipedia.org/wiki/Regular_language" rel="nofollow noreferrer">Wikipedia, includes explanation about squares and irregular regexes</a></li> <li><a href="https://stackoverflow.com/q/6718202">What is a regular language?</a></li> </ul>
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. This table or related slice is empty.
PostTypePostTypeId
1. PTTagWiki
UserLastEditorUserId
1. This table or related slice is empty.
UserOwnerUserId
1. USPhilip Liberato
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. This table or related slice is empty.
CommentsPostId
1. This table or related slice is empty.

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.