تمرینات را روی کاغذ نوشته و سپس عکس گرفته و نهایتا تا سه شنبه 14/10/1395 برای استاد ایمیل کنید

ایمیل ایشان:

b.tanoori.st@Gmail.Com

حجم فایل:33.7مگابایت

نوع فایل:pdf

نام فایل: حل تمرین

جهت دانلود روی لینک زیر کلیک نمایید:

 https://drive.google.com/file/d/0B1gG1Mpj5aojTzZwU0RoN2tfTXM/view?usp=sharing

تمرینات زیر در pdf بالا حل شده اند:

صفحه 63 فصل 2
3. Find a dfa that accepts the complement of the language defined by the nfa in Figure 2.8.
4. In Figure 2.9, find δ* (q0,1011) and δ* (q1,01).
6. For the nfa in Figure 2.9, find δ*(q0, 1010) and δ* (q1,00).
12. Which of the strings 00, 01001, 10010, 000, 0000 are accepted by the following nfa?

صفحه 70 فصل 2
2. Convert the nfa in Exercise 12, Section 2.2, into an equivalent dfa.
3. Convert the following nfa into an equivalent dfa.
5. Is it true that for any nfa M = (Q,Σ,δ,q0,F) the complement of L(M)is equal to the set {w ∈ Σ*: δ*
(q0,w) F= Ø}? If so, prove it. If not, give a counterexample.
8. Find an nfa without λ-transitions and with a single final state that accepts the set {a}∪{bn: n ≥1}.

صفحه 77 فصل 2
1. Minimize the number of states in the dfa in Figure 2.16.
2. Find minimal dfa's for the following languages. In each case prove that the result is minimal.
(a) L = {an bm> :n≥2,m≥1}.
4. Minimize the states in the dfa depicted in the following diagram.

صفحه 92 فصل 3
4. Find dfa's that accept the following languages.
(a) L (aa* + aba*b*).
(b) L (ab (a + ab)* (a + aa)).
10. Find regular expressions for the languages accepted by the following automata
13. Find a regular expression for the following languages on {a, b}.
(a) L = {w : na (w) and nb (w) are both even}.
(b) L = {w :(na (w) - nb (w)) mod 3 = 1}.

صفحه 102 فصل 3
4. Construct right- and left-linear grammars for the language
L = {anbm : n ≥ 2, m ≥ 3}.
6. Construct a right-linear grammar for the language L ((aab*ab)*).

صفحه 125 فصل 4
3. Show that the language L = {w : na (w) = nb(w) } is not regular. Is regular?
4. Prove that the following languages are not regular.
(a) L = {anblak : k ≥ n + l}.
(b) L = {anblak : k ≠ n + l}.
(c) L = {anblak: n = l or l ≠ k}.
(d) L = {anbl : n ≤ l}.
(e) L = {w: na (w) ≠ nb (w) }.
(f) L = {ww : w ∈{a, b}*}.
(g) L = {wwwR : w ∈ {a, b}*}.
5. Determine whether or not the following languages on Σ = {a} are regular.
(a) L = {an: n ≥ 2, is a prime number}.
(b) L = {an: n is not a prime number}.
(c) L = {an: n = k3 for some k ≥ 0}.
(d) L = {an: n = 2k for some k ≥ 0}.
(e) L = {an: n is the product of two prime numbers}.
(f) L = {an: n is either prime or the product of two or more prime numbers}.
(g) , where L is the language in part (a).
7. Show that the language
14. Prove or disprove the following statement: If L1 and L2 are non regular languages, then L1 ∪ L2 is
also non regular

صفحه 137 فصل 5
3. Give a derivation tree for w = abbbaabbaba for the grammar in Example 5.2. Use the derivation
tree to find a leftmost derivation
20. Consider the grammar with productions

صفحه 148 فصل 5
1. Find an s-grammar for L (aaa*b + b).
6. Show that the following grammar is ambiguous.