а вот ещё такой есть Шалыто

[juan_gandhi]

За каким-то хреном ознакомился с историей вопроса, и, в частности, как он громит Дмитрия Павлова, как бы выпускника ЛИТМО.

По-моему, Шалыто этот - обычный советский идиот. Как это у него получается, что он конечные автоматы изобрёл?
Извините если что.

Comments

[das-mutante.livejournal.com]

В курсе.

[ivan-gandhi.livejournal.com]

Очень хорошо.

Извините, очень сложно разговаривать практически с полным анонимом. Не знаешь, на чём основываться, какое знание общее, а какое нет.

[das-mutante.livejournal.com]

Я пытался донести 2 мысли:

1) на собеседовании по программированию эту формулировку можно интерпретировать как "написать программу, решающую конкретную задачу -- проверку скобок" и как "доказать, что граммар L ::= '(' L ')' | C непарзим FSM-ом.". И что контекст предполагает предпочтение первой.

2) вносить ограничения на произвольно выбранные параметры -- замечательное средство в проектировании.

function genRE($depth)
{
	$chr = "[^()]";
	if ($depth == 0)
		return $chr;
        return "(" . $chr."*" .
        	"([(]" . $chr."*" . genRE($depth - 1) . $chr."*" . "[)])*" .
        	$chr."*" . "|" . $chr . "*)*";
}

function genTest(&$ok)
{
	$len = 9;
	$s = "()a";
	$test = "";
	$p = 0;
	for ($i = 0; $i < $len; $i++) {
		$c = $s[rand(0,3)];
		if ($p >= 0) {
			if ($c == "(") $p++;
			if ($c == ")") $p--;
		}	
		$test = $test . $c;
	}
	echo "p=$p".$p===0;
	$ok = ($p <> 0)? 0 : 1;
	return $test;
}

function runTest($dry, $re)
{
	$tm0 = microtime(true);
	$run = 0;
	while (true) {
		$tm1 = microtime(true);
		if ($tm1 - $tm0 >= 3.0)
			break;
		if (!$dry) {
			$test = genTest($ok);
			$r = preg_match($re, $test);
			if ($r <> $ok) {
				print "FAILED: $test";
			}
		}	
		$run++;
	}
	return $run / ($tm1 - $tm0);
}
	print "Timing...";
	$re = "/^(" . genRE(300) . ")*$/";
	$speed = runTest(true,$re);
	$speed = 1.0/ (1.0/runTest(false,$re) - 1.0/$speed);
	print "speed: $speed checks per second";  // speed: 1945 checks per second w/o zend

[das-mutante.livejournal.com]

А ещё -- вы живёте в мире, где все возможные вычислители -- FSM, сам мир FSM, да сами Вы FSM, фантазирующая о более мощных машинах.

[ivan-gandhi.livejournal.com]

Это лишь одна из теорий. Начало берёт в интересном предположении, что теория множеств, скажем, ZF, применима к окружающему нас миру - всё это было бы мило, но она неприменима даже к самой себе.

[das-mutante.livejournal.com]

Это не "всего лишь" и не связано с ZFC. Это следствие конечности материи и энергии в нашей вселенной.

[das-mutante.livejournal.com]

> она неприменима даже к самой себе.

Если Вы намекаете на теоремы о неполноте, то зря: невозможность доказать непротиворечивость логики в ней самой обречена на неудачу уже только потому, что в противоречивой логике выводимо любое утверждение. А для других доказательств вполне применима.

[das-mutante.livejournal.com]

Кстати, доказательство, являясь обьектом в физическом мире, конечно, а значит, написано на регулярном языке и изучаемо разрешимой монадической логикой навроде WS2S http://www.brics.dk/mona/publications.html

[ivan-gandhi.livejournal.com]

О, спасибо! Ещё одно окно в большой мир. Буду читать.