automata-theory

1熱度

2回答

讓語言L_n具有字符集Sigma = {a_1，...，a_n}。 L_n恰好包含那些包含一些奇數次字符的單詞。等價地，如果L_n^i是每個包含奇數個a_i的字的語言，則L_n = L_n^1 union ... union L_n^n。我已經產生了接受L_n和2^n狀態的DFA的NFA，我現在需要證明這是接受此語言的最小DFA。我給出的提示假設有爲k < 2^n種狀態，它接受L_N的DFA，

2熱度

1回答

DFA可以識別多少種語言？

根據Sipser的「計算理論導論」：如果A是機器M接受的所有字符串的集合，我們說A是機器M的語言並且寫L（M）= A。 M識別A ...機器可以接受多個字符串，但它總是隻識別一種語言。以及我們說M如果A = {w | M接受w}。我猜這個問題已經被回答了，但是我想知道是否有人有任何想法，如果有什麼有趣的話我們可以說關於常規語言的子集，如果我們可以說，原始DFA可以識別它們，並且原始DFA與識別

0熱度

1回答

推導和推導樹之間的關係是什麼？

這是寫在烏爾曼書，但我沒有站得很好它是如何工作的。任何人都可以在簡單的情況下解釋嗎？我真的很高興。

0熱度

1回答

非確定下推自動機不同的圖

在介紹計算書的理論，語言狀態圖給出：我知道有可能是替代圖，但我懷疑的解決方案，我發現可能是錯誤的，這是比原來的稍有不同：我希望我的解決方案的任何計數器輸入。

0熱度

2回答

對於L = {a ^（n）b ^（n）c ^（n）| n> = 1}的PushDown自動機（PDA）

我正在試圖構建非上下文的下推自動機的愚人差事自由語言L = {a ^（n）b ^（n）c ^（n）| n> = 1}並考慮兩種方法。第一種方法： - 我認爲，每一個「A」的字符串我會推3「」進棧和字符串中的每一個「B」，我會彈出2 'a'現在對於字符串中的每個'c'，我仍然會在堆棧中有'a'。問題與第一種方法： -產生的語言成爲這樣的L = {A ^（P）b ^（M）C ^（n）的| P> =

-1熱度

1回答

提供生成以下語言的上下文無關文法

提供生成以下語言的上下文無關文法。在所有部分中，字母表Σ是{x，s}。 {w | w開始並用不同的符號結束}

0熱度

1回答

正則表達式，其中字母b從未三倍

我需要關於正則表達式的幫助。我想要一個正則表達式，其中字母b從來沒有三倍。這意味着沒有字包含其中的子字符串bbb。語言只包含字母{A，B}

1熱度

1回答

查找上下文無關語法（CFG）

給出一個上下文無關語法H，該語法生成語言 M = {a^m b^n | 2m> n> m}。 ' 提示：m不能爲0，因爲在這種情況下2m = m。 m不能是1，因爲在這種情況下2> n> 1，這樣的自然數n不存在。所以語言M中最短的字符串是aabbb。對於較長的字符串，您需要確保 bs的數量n和m的數量滿足2m> n> m。

0熱度

1回答

自動機理論中的正則表達式？

我有以下的語言和正則表達式【W∈{A，B} *：W的BAB作爲前綴，並巴巴作爲後綴} 答：正則表達式= BAB（一個∪b）*巴巴∪ 爲什麼加粗部分需要巴巴∪bababaa？

0熱度

1回答

當r和r的DFA被確定時，發現r *的DFA

我想要說明當定義r的r和DFA時，找到r *的DFA的方法的例子。以及如何思考？我讀了一本教科書，但我不明白。謝謝。