首页 > > 详细

讲解 Consider the following εNFA:程序语言

Theories of Computation: Summative Assignment 1
due on Mon 12 Feb, 15:00
Exercise 1. Consider the following εNFA:
(A) Give the NFA that is achieved by removing the above εNFA’s ε-transitions (using the algorithm taught),
[2 points]
(B) Give the DFA that is achieved by determinising your answer to (A), [2 points]
(C) Give the minimal DFA that is achieved by minimising your answer to (B). [2 points]
Exercise 2. Consider the language L of those words matched by a

(ba)

that contain twice as many a’s as b’s (e.g.
aba, aababa are accepted, but not aaba or baa). Show that this language is not regular. [4 points]
Exercise 3. For any regular expression E and n ∈ N, we write En as an abbreviation for the regular expression
n times
z }| {
E . . . E .
In particular, considering the alphabet {x}, we have the regular expressions A = x
3 and B = x
7
, where A only
accepts the word xxx and B only accepts the word xxxxxxx. It turns out that for every natural number n > 11, we
can express x
n by only concatenating the expressions A and B (e.g. x
12 = AAAA and x
38 = BABBBB).
(A) Show that this is the case for x
13 and x
14
, [2 points]
(B) Prove that this is the case for all n > 11 by using (course-of-values) induction. [3 points]

联系我们
  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-21:00
  • 微信:codinghelp
热点标签

联系我们 - QQ: 99515681 微信:codinghelp
程序辅导网!