
Theory of Computation Theoretical Computer Science  Automata Theory, Computability Theory, and Computational Complexity Theory 
 LinkBack  Thread Tools  Display Modes 
December 6th, 2010, 08:18 AM  #1 
Joined: Dec 2010 Posts: 2  Regular Language
I have got a problem ,like ************************************************** ************************************************** ************************************************** ********* By an edit operation for a word we mean an operation of one of the forms: • delete(i) where i is a position in w. • insertafter(a,i) where i is a position in w and a is a letter. • insertbefore(a,i) where i is a position in w and a is a letter. • Change(b,i) where i is a position in w and a is a letter. The result of applying an edit operation o to a word w=w1......wn is defined as follows: • If o is delete (i) and 1<= i <= w then the result is o(w) = w1....wi1wi+1.......wn. • If o is insertafter (a,i) and 0<= i <= w then the result is o(w) = w1....wiawi+1.......wn. • If o is insertbefore (a,i) and 0<= i <= w then the result is o(w) = w1....wi1awi.......wn. • If o is change (b,i) and 1<= i <= w then the result is o(w) = w1....wi1bwi+1.......wn. If the argument to an edit operation is out of range(e.g. i is larger than the number of positions) then we take its result when applied to w as w: i.e. it is a “noop”. The result of applying a sequence s of edits o1......on to a word w is simply the result of applying the operations in order: it is wn where w0=w and wi+1 =oi(wi). We write s(w) for the result of applying sequence s to word w. For two languages L, L’ and an integer k, say that L is kcontained in L’ if for every word w belongs to L and every sequence s of at most k edit operations, s(w) belongs to L’. For example, let L= {w belongs to {0,1}*  w contains at least 2 1’s} and L’= { w belongs to {0,1}*  w contains at least one 1}. L is 1contained in L’, since applying a single edit to any word in L results in a word in L’. (a) Show that for each k there are regular languages L and L’ such that L is kcontained in L’ but not k+1 contained in L’. (b) For which languages L it is true that L is 1contained in itself. (c) Give an algorithm for determining, given an integer k and two DFAs A, A’, whether or not the language accepted by A is kcontained in the language accepted by A’. Prove that your algorithm is correct. (d) Determine whether the following function is computable: the function takes an input DFAs A and A’, and determines the largest k for which L(A) is kcontained in L(A’), or returns infinity if L(A) is kcontained in L(A’). If it is not computable, prove that it is not. If it is computable, give an algorithm(in pseudo code) that computes it. (e) Consider the problem of determining, given NPDAs A1 and A2 whether the language of A1 is 2contained in the language of A2. Is this problem decidable? If yes, give an algorithm for deciding it. If not, prove undecidability. How about for larger values of k? ************************************************** ************************************************** ************************************************** ********************************** please help me how to solve this problem 
My Computer Forum is free to register and we welcome everyone! 

Tags 
language, regular 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
proving regular languages  i have a hard one!  kellyk  Theory of Computation  1  April 29th, 2012 09:58 PM 