Automata Theory: Prob # 66 from practice booklet

[endlessdream]

I go through the GR 0329 practice booklet, and found this problem very intricate (though seems easy). I would be grateful if you give a convincing explanation.

66. Consider languages L and L1, each over the alphabet {a, b} where
L1 = {w|w contains some x is MemberOfSet L as a substring}

Which of the following must be true about L and L1 ?
I. If L is regular, then L1 is regular.
II. If L is context-free, then L1 is context-free.
III. If L is recursive, then L1 is recursive.
(A) I only (B) III only (C) I and III only (D) II and III only (E) I, II, and III


ALSO, I dont have any idea about some other problems (though I spent ample time over these):

# 42 : This problem confused me totally.... pls give a hints !
# 45 : convergence of Newton's Method
# 61 : decidibility of problem
# 47 : Turing Machine

Thnks in advance...

[CalmLogic]

For a previous discussion of #66:

http://www.google.com/search?hl=en&rls=com.microsoft%3A*%3AIE-SearchBox&rlz=1I7DKUS&q=site%3A+urch.com+%22L1+is+ context-free%22

[gttts23]

Except for 45, all problems requires reasonable familiarity with automata, formal languages and computability. I know that the answers I give are a bit too formal, ask a specific question and I'll try to answer.

Problem 66

I: L is regular - there exists a regular expression X for L. The regular expression (a+b)*X(a+b)* represetns L1.

II: L is context-free, then there exists a context-free grammar G for L. We'll create a CFG for L1, this grammar will be identical to G except for a new start variable S', a new variable X and a few additional productions

S' -> XSX
X -> a|b|TheEmptyWord

III: L is recursive, then there exists a Turing machine M that decides L. We'll create a new nondeterministic TM M' that decides L1. M' will choose nondeterministically a start and end position and will run M on the word between the selected positions.

Clearly, M' has an accepting run on w iff w contains a subword that is accepted by M, or in other words M' accepts a word w if it has a subword in L == the definition of L1.

The "trick" is the same for all three cases. Given L is a regular/context-free/decidable, take the automata/grammar/TM that accepts/generates/decides it and try to modify it to create an automata/grammar/TM for L1.

Problem 42

I'll write & for AND and | for OR. AND and OR without NOT cannot represent all the boolean functions. But what kind of functions can they represent.

The easy item is I. The formula (p1&p2&p3)|(p1&p2&p4)|(p2&p3&p4) is true if one of its terms is true.

But can AND and OR express II and III? The answer is no. Intuitively the reason for that is that without a NOT operation, once we have a satisfying assignment we can take any of the variables that are assigned false and flip them to true and we are still left with a satisfying assignment.

So AND and OR can define functions such as: at least k of the variables are true. but they cannot express functions such as 'exactly k are true' or 'exactly an odd number of variables is true' because once we have a satisfying assignment we can flip one of the variables that are assigned false and still have a satisfying assignment.

Problem 47

We are given a turing machine M, a blank input and an integer n. We are asked whether it is possible to decided each of the three problems.

I: Yes. Just simulate M for n steps and then stop. If M stopped return YES, otherwise return NO. This is easily decidable because we have some known time limit to observe M and then to stop.

II: No. The halting problem can be reduced to II. Given a Turing machine M and a word w, we can create a new Turing machine Mw that will run M on w and if M stops will print 1. Assuming II was decidable we give it as input Mw and 0.

III: Yes, but this quetion is harder. Recall that a configuration of a Turing machine is the state of the machine, the location of the head and the content of the tape.

If M does not scan more than n tape squares then it can only have a limited number of different configurations :

MAX_CONFIGURATIONS(n) := <number of states> x n x 3^n.

That means that if M scanned only n sqaure than it is stuck in a loop and will never scan more than n squares. So the decision algorithm is: Given M and n, simulate M for MAX_CONFIGRATIONS(n) steps. If M scanned more than n tapes return YES, otherwise return NO.

Problem 61

I: Yes. This is the equivalent to calculating PI upto |w| digits.

II: No. This is equivalent to the halting problem. Given an M and a w, create Mw that simualtes M on w and if M stops ouputs 3.141. Clearly, Mw outputs a prefix of PI iff M halts on w.

II: No. This is also undecidable. Again, Given an M and a w. Create Mw such that if the input is other than 3.141 it halts and outputs YES. If, on the other hand, the input is 3.141 it runs M on w and outputs YES if M halts.
Again, M halts on w iff the outputs of Mw on all prefixes of PI are the same.

[endlessdream]

Hi gtts...
thanks for your nice explanation.

[brianhead]

I have a question about this:
if L is (a+b)*, then L is reguar language, L1 could be a^nb^n which is context free language.
How to solve this problem. Do I have any misunderstanding here?

[R0jkumar]

If L is (a+b)* then L1 cant be a^nb^n, since L1 = (a+b)*L1(a+b)* = (a+b)*(a+b)*(a+b)* = (a+b)* which is regular.

[ethanph]

Originally Posted by R0jkumar

If L is (a+b)* then L1 cant be a^nb^n, since L1 = (a+b)*L1(a+b)* = (a+b)*(a+b)*(a+b)* = (a+b)* which is regular.

hi, do you mean that (a+b)* is regular, but it's substring a^nb^n is not regular?

[brianhead]

Originally Posted by R0jkumar

If L is (a+b)* then L1 cant be a^nb^n, since L1 = (a+b)*L1(a+b)* = (a+b)*(a+b)*(a+b)* = (a+b)* which is regular.

I do not quite understand why L1 can not be a^nb^n? Would you like to give a little more details?

[taro_curly]

A regular language is a language that can be recognized using some finite state machine (FSM), either a DFA or an NFA.

Neither of them has any memory. Therefore, neither can count. (to see why, try to construct a FSM that will accept whenever it receives exactly n inputs, where n is a variable). In the absence of any memory, it is impossible to keep track of whether equal numbers of a and b have been seen so far.

Hence, a^nb^n is not a regular language.

[R0jkumar]

Originally Posted by ethanph

hi, do you mean that (a+b)* is regular, but it's substring a^nb^n is not regular?

From the very definition of L1, a string x is in L1 if and only if there is a substring of x that is in L. Your language a^nb^n certainly has a substring that belongs to L and hence a^nb^n is a subset of L1 but not the entire set. In other words by using L1 = a^nb^n you are showing that if x belongs to L1, then x contains a substring that belongs to L but you have to show the converse as well. That is you have to show that given a string x belonging to L, if you add any string at the beginning and at the end , you should be able to get a string in L1.But thats wont be true in the case of L1=a^nb^n since if i take any string of a's and b's and add any string at the beginning and the end, i am not necessarily going to get a string of a's followed by b's such that the number of a's and b's are equal. Hope that helps.