Talk:Powerset construction

Very nice example and description.

Small remark: I don't see the purpose of the ∅ state and the transition from state {4} in the DFA of the example:

It's rather confusing. A DFA does only accept an input if it has reached the end of the word. For example, the input '0001' would cause the sample DFA to block at {4} (having an input but no matching transition) and thus reject the word. --Code Wizard 23:45, 27 Jan 2005 (UTC)

Hi Code Wizard, thanks for your feedback. To answer your question, technically, this is not the case — this is only a convenient convention commonly used in drawings of DFAs. In the formal definition of a DFA, it is specified that there is exactly one transition out of each state on each character. If the edges are not drawn, it's assumed they lead to some inescapable non-accepting state such as the one drawn above. I chose to be more explicit about this in this instance, for clarity. Deco 07:06, 29 Jan 2005 (UTC)

"C_ε(q) is the ε-closure of q, i.e. the set of all states reachable from q by one or more ε-transitions." Shouldn't this be "zero or more?" Otherwise s may not be contained in the start state (for instance). 129.93.158.50 (talk) 18:52, 15 September 2008 (UTC)

I think, i would be rather a nonsense to say that a state is reachable by no transitions at all. And as far as i understand, closure of q includes q in any case. --91.202.128.73 (talk) 01:45, 25 October 2009 (UTC)

Merge with Nondeterministic finite state machine/Proofs

It seems that Nondeterministic finite state machine/Proofs contains little but a symbolic version of the method given here. In addition, the article name 'Nondeterministic finite state machine/Proofs' does not conform to Wikipedia naming conventions. Therefore I propose that any material in that article that is not already here be explained in words rather than symbols for readability and merged with this article.--RDBury (talk) 03:14, 11 December 2009 (UTC)

It seems to have been done. I'm removing the tag. → Synook _讲讲 03:55, 24 December 2009 (UTC)

Tone?

In this (very helpful, by the way) article there are sentences such as 'We need to ...; how do we ensure this? We create a new node', which are in a more or less educational tone. I'm not an experienced Wikipedia user, so I'm not sure whether this is conforming to its standards as to being 'encyclopedic'. It sure is in the normal sense, but I've rarely seen other Wikipedia articles written in this tone - it could've been written like 'to ensure this, we create a new node', for example. Just wondering. Wyverald (talk) 13:49, 7 November 2010 (UTC)

I also agree that this article is too verbose. One has to rewrite more concise description of construction. (Ashutosh Gupta)

I too noticed this, and I just tagged the article for the tone and for not having many references. While the content seems clear enough the prose style is decidedly non-encyclopedic.Eniagrom (talk) 20:45, 24 February 2011 (UTC)

It's a standard textbook topic. It has enough references. Tijfo098 (talk) 22:36, 29 April 2011 (UTC)

Regarding the tone: I don't think the word "we" can be entirely eliminated. I admit that it's a little uncomfortable, but it's a style I've seen before in mathematical papers, and it's supported by the guidelines at WP:TONE. I can't see how to rewrite it without it becoming very clumsy (e.g. using the phrase "the automaton" many times, and recasting a lot of "we can..." constructions in the passive voice). So leaving it as is seems to be the lesser evil. Perhaps there are some small changes that could be made, but I'd propose removing the "tone" tag unless someone has a clear idea of how to do a rewrite. Jowa fan (talk) 00:00, 30 April 2011 (UTC)

"We" is widely used in theoretical computer science papers and even encouraged. As Jowa said it avoids clumsy constructions.Ashutosh Gupta (talk) 00:11, 30 April 2011 (UTC)

Well, I rewrote the 1st section to avoid it, but some passive voice had to be used instead (pun intended). Tijfo098 (talk) 00:14, 30 April 2011 (UTC)

Also, the current official guideline (if we can call a page almost continuously locked down due to edit wars that) is WP:FIRSTPERSON. Tijfo098 (talk) 11:50, 30 April 2011 (UTC)

Too many examples?

I like the first and last examples ("example" and "example 3") because they label the DFA states with the subsets. Example 2 doesn't do this and also uses DFA minimization, which it doesn't explain. Perhaps that example/section can be omitted without much loss in this article? Tijfo098 (talk) 23:42, 29 April 2011 (UTC)

I agree with you. Example 2 doesn't add anything and adds clutter. Ashutosh Gupta (talk) 00:00, 30 April 2011 (UTC)

Construction section

NFA may contain more than one initial states and in this section it is assumed that NFA has one state.Ashutosh Gupta (talk) 08:39, 2 May 2011 (UTC)

I looked into some books and course materials. They all start with single state. It seems this section follows the standard definition. I am wondering why they don't allow more than one initial state?Ashutosh Gupta (talk) 09:42, 2 May 2011 (UTC)

I added a bit about multiple initial states. This is needed in Brzozowski's algorithm, for instance. —David Eppstein (talk) 15:16, 2 May 2011 (UTC)

worst-case runtime complexity for constructing the DFA from an NFA via Rabin-Scott

I would have thought the worst-case runtime complexity for constructing the DFA from an NFA via Rabin-Scott is $\Theta(2^n \times n \times b)$, with $b$ being the maximal branching, not $\Theta(2^n)$.

Here is a discussion about it: http://cstheory.stackexchange.com/questions/27794/what-is-the-worst-case-runtime-complexity-to-transform-a-nfa-to-dfa-via-rabin-sc — Preceding unsigned comment added by DavidFarago (talk • contribs) 11:22, 12 December 2014 (UTC)

Reference Source

The article refers to Lupanov, Oleg B. (1963). "A comparison of two types of finite sources". Problemy Kibernetiki. 9: 321–326. But I couldn't find access to this article, either the original version written in Russian or translated version.

All I have found is that the author's name is О. Б. Лупанов, the article 's title is «О сравнении двух типов конечных источников», and the journal's name is проблемы кибернетики, Volume 9 (Вып. 9).

Can anyone help accessing this reference source? — Preceding unsigned comment added by Ritsuka314 (talk • contribs) 01:32, 10 November 2023 (UTC)