Topic: 计算理论问题紧急求解,明天早晨GF就要了,知道的DX务必帮忙.先谢了. ^_* @佛州华人论坛:佛州枫下论坛 The Rolia Forum of Florida

工作学习 / IT技术讨论 / 计算理论问题紧急求解,明天早晨GF就要了,知道的DX务必帮忙.先谢了. ^_*Let A be a language consisting of finitely many strings.
1)Prove that A is regular.
2)Let p be the maximum length of any string in A. Prove that every deterministic finite automaton (DFA) that recognizes A has at least p+1 states. -smallrainrain(小雨雨); 2002-11-6 {234} (#840678@0)

没有DX知道, 失望ING... UP 一下. ^_* -smallrainrain(小雨雨); 2002-11-6 (#840688@0)
写成中文还能勾起些回忆，翻书来找找答案，英文嘛……，是什么正则有限自动机吧，老啦，想不起来了，查查编译理论吧。 -wooway(纯洁中文运动<加东区>); 2002-11-6 (#840717@0)
Can not be sure I am right as I learned this staff 10 years ago. Anyway, here is my answer:1. Regular language can be recongized by the DFA, right? A can be recongized by a DFA as there are finitely string in A.
2. to recongize p characters you need p+1 states in the DFA. -kingmay(五月王); 2002-11-6 {183} (#840734@0)

Regular language is DFA, but your answer seems too simple. Anyway, thanks first. 那位DX知道更准确的答案? ^_* -smallrainrain(小雨雨); 2002-11-6 (#840747@0)
是interview要用吗？你要完整的答案还是提示？我打字不快。 -smallwhale(喝不了咖啡); 2002-11-6 (#840934@0)

还有人知道么?急呀急. ^_^ -smallrainrain(小雨雨); 2002-11-6 (#840779@0)
1. a. any limited length string can be recongized by a DFA. b. A, a language that is consisted of definitely strings, can be recongized by a DFA that is composed by the DFAs that recongized the those strings -kingmay(五月王); 2002-11-6 (#840799@0)
2. let S is the string with a length P, to recongized S you need a P+1 states DFA. So a DFA recongized A has at least P+1 states. I can not go more details as I can not remember the terms. Hope this is helpful. -kingmay(五月王); 2002-11-6 (#840806@0)
用这个题目作Interview的话,国内来的专业IT,没有多少能找到工作,帮你UP一下吧,看在你为了女朋友的份上,好好对你女朋友吧! -reis(李嘉欣); 2002-11-6 (#840908@0)

@Florida