My Computer Forum Computer Science Forum

Go Back   My Computer Forum > Computer Science Forum > Theory of Computation

Theory of Computation Theoretical Computer Science - Automata Theory, Computability Theory, and Computational Complexity Theory


Closed Thread
 
LinkBack Thread Tools Display Modes
December 6th, 2010, 07: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....wi-1wi+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....wi-1awi.......wn.
• If o is change (b,i) and 1<= i <= |w| then the result is o(w) = w1....wi-1bwi+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 “no-op”.
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 k-contained 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 1-contained 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 k-contained in L’ but not k+1 contained in L’.
(b) For which languages L it is true that L is 1-contained 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 k-contained 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 k-contained in L(A’), or returns infinity if L(A) is k-contained 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 2-contained in the language of A2. Is this problem decidable? If yes, give an algorithm for deciding it. If not, prove un-decidability. How about for larger values of k?

************************************************** ************************************************** ************************************************** **********************************

please help me how to solve this problem
ajitjjn is offline  
 

My Computer Forum is free to register and we welcome everyone!

Closed Thread

  My Computer Forum > Computer Science Forum > Theory of Computation

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 08:58 PM





Copyright © 2018 My Computer Forum Forum. All rights reserved.