computation-theory

2熱度

1回答

我有一列我想分割的值（整數）B非空子列表不改變他們最初的命令。我們的目標是調整文本的大小以適應其定義的區域。每個子列表都會有一個與其相關的指標：其值的總和。我想盡量減少的差異DIFF之間的最大的總和與所有子列表中最小的總和。這將允許我將文本分成幾行幾乎相同的文本。 EDIT 如所建議的，它也將工作以最小化最大總和，因爲這將導致最小化的文本行的最大長度。實例：給出的列表L = {2,3,4,5

0熱度

2回答

瞭解CFG的基本知識

在Sipser的書中剛剛開始關於CFL的章節，並且已經不瞭解基礎知識。讓這成爲一些語言的語法： S -> A0A A -> 00A | 11A | 10A | 01A | e 我真搞不清楚這個A0A部分。這是否意味着從0開始的左手側應始終與右手側相同。這是否意味着00011或000不是用這種語言呢？

-1熱度

1回答

用於預期的硬幣擲幣的DFA

我試圖構造這個問題：一個公平的硬幣被拋出，直到兩個頭連續出現。擲硬幣的次數是多少？爲語言L + {w | w具有11作爲子字符串}設計DFA 使用此DFA作爲馬爾可夫鏈來計算所需的概率。（具體來說，對於每個狀態q，如果q是開始狀態，設P（q）爲達到接受狀態的概率。）我在設計DFA時遇到問題，需要一些幫助。

0熱度

1回答

可判定語言（計算模型）

我需要證明L是否可判定與否： L = {< M> | M是TM和L的（M）的結合和對H_TM是在RE} （H_TM = {< M，W> | M是上瓦特}停止一個TM）

2熱度

3回答

我們如何知道NP完全問題是NP中最難的？

我知道如果你可以從「每一個」問題做一個多項式時間減少，那麼它證明了這個問題至少和NP中的每個問題一樣困難。除此之外，我們怎麼知道我們發現了NP中的每個問題？難道不存在我們在NP中未發現或證明存在的問題，但是不能將其減少爲任何NP完全問題？或者這仍然是一個懸而未決的問題？

0熱度

2回答

喬姆斯基規範格式轉換算法

當我們想要將語法轉換爲喬姆斯基規範形式時，爲什麼我們要添加一個新的起始狀態S0 - > S？如果我們不這樣做會出什麼問題？起初我以爲這是因爲epsilon規則。但是我們不會從啓動變量中刪除一個epsilon規則。那麼，添加S0 - > S的好處是什麼？謝謝

0熱度

1回答

正則語言

我所遇到的在那裏他們指出的語言由 L = {WW - [R表示許多論壇| W - [R是W的反向和W屬於（0,1 ）*} 不是正常的。抽水引理也證明了這一點。但是我能夠爲此寫一個正則表達式，其中我使用了與this鏈接中給出的相同的邏輯。檢查：（0 + 1）* 11（0 + 1）* +（0 + 1）* 00（0 + 1）* 邏輯中是否有缺陷？或者我可能錯過了一些東西。感謝提前:)

3熱度

2回答

上下文無關語法的算法

我試圖設計一個算法，它將一個CFG G和一個終端符號a作爲輸入，並且如果S（G的開始規則）可以生成一個開始的句子形式，與。即如果在（T U N）*中有一個串α使得S => *aα，否則它輸出否。例如，如果語法是S - > [S] | SS | ε，如果a =]，答案是否定的。我不在尋找代碼，我只是想了解我應該如何在僞代碼中處理這個主題。

1熱度

1回答

構建一個上下文無關文法喬姆斯基範式語言

我試圖構造一個CFG喬姆斯基範式以儘可能少的生產儘可能接受含有唯一的字符串^ 21的語言。我明白，我可以轉換的S - > AAAAAAAAAAAAAAAAAAAAA A - >一個但沒有任何其他的方式來縮短該語言然後將其轉換成Chomsky範式？

0熱度

2回答

將L = {a * b *}劃分爲常規語言嗎？

將L = {a * b *}分類爲常規語言嗎？我很困惑，因爲我知道L = {a^n b^n}不規則。克萊恩明星有什麼不同？