Automata. A bit long. Please answer carefully and in detail. 9. Let LI and L2 be
ID: 3912624 • Letter: A
Question
Automata. A bit long. Please answer carefully and in detail.
9. Let LI and L2 be arbitrary languages, subject to the specification in either (i) or (ii). Consider the following four questions: (Q1) Does Li-L2 contain a given fixed word w? (Q2) Is LI-L2 empty? (Q3) Does LinL2 contain a given fixed word w? (Q4) Is LinL2 empty? For each of these four questions explain with reasons whether the general problem is recursive, not recursive but r. e., or non-r. e., provided (i) Both Li and L2 are recursive. (ii) Li is r. e., but not recursive and L2 is recursive.Explanation / Answer
i) L1 and L2 are recursive languages
Q1) Does L1-L2 contain a fixed word w?
L1 - L2 = L1 intersection L2c
Recursive languages are closed under complementation and intersection
=> L1 intersection L2c is Recursive
=> L1 - L2 is recursive.
If the language is recursive then we can construct a turing machine that always halts. If w belongs to L1 - L2, then turing machine halts and shout accepted, otherwise halts and shout rejected.
=> problem is recursive.
Q2) Is L1 - L2 empty?
L1 - L2 = L1 intersection L2c
Recursive languages are closed under complementation and intersection
=> L1 intersection L2c is Recursive
=> L1 - L2 is recursive.
If the language is recursive then we can construct a turing machine that always halts. The turing machine accepting the language will halt and reject on all input.
=> problem is recursive.
Q3) Does L1 intersection L2 contain a fixed word w?
As we know recursive languages are closed under intersection,
L1 intersection L2 is recursive.
If the language is recursive then we can construct a turing machine that always halts. If w belongs to L1 intersection L2, then turing machine halts and shout accepted, otherwise halts and shout rejected.
=> problem is recursive.
Q4) Is L1 intersection L2 empty?
As we know recursive languages are closed under intersection,
L1 intersection L2 is recursive.
If the language is recursive then we can construct a turing machine that always halts. The turing machine accepting the language will halt and reject on all input.
=> problem is recursive.
ii) L1 is r.e but not recursive, L2 is recursive.
Q1) Does L1 - L2 contain a fixed word w?
L1 - L2 = L1 intersection L2c
L1 is recursive enumerable but not recursive.
Recursive languages are closed under complementation => L2c is recursive
=> L2c is recursive as well as recursive enumerable.
=> L1 intersection L2c is recursive enumerable but not recursive.
=> L1 - L2 is recursive enumerable but not recursive.
If the language is recursive enumerable but not recursive then we can construct a turing machine that always halts If w belongs to L1 - L2, otherwise for sme input which does not belong to L1 - L2 it might enter a loop.
=> problem is recursive enumerable but not recursive.
Q2) Is L1 - L2 empty?
L1 - L2 is recursive enumerable but not recursive.
=> problem is recursive enumerable but not recursive..
Q3) Does L1 intersection L2 contain a fixed word w?
L1 is recursive enumerable but not recursive.
L2 is recursive as well as recursive enumerable.
L1 intersection L2 is null
=> L1 intersection L2 is regular
=> L1 intersection L2 is recursive and recursively enumerable
=> problem is recursive enumerable.
Q4) Is L1 intersection L2 empty?
L1 is recursive enumerable but not recursive.
L2 is recursive as well as recursive enumerable.
L1 intersection L2 is null
=> L1 intersection L2 is regular
=> L1 intersection L2 is recursive and recursively enumerable
=> problem is recursive enumerable.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.