Help With Some Theory Questions

[booyaksha58]

I need help with the following true or false questions:

 

1.The Intersection of two context-free languages is recursive.

2.For an arbitrary regular language L, the set of all strings in L that have even length forms a language that is not recursive.

3. If L is accepted by a PDA then L is accepted by a PDA that has no compatible transitions.

 

 

For clarification purposes, recursive means a that a turing machine can decide the language. Recursive enumerable means that a turing machine can recognize the language. PDA = push down automaton. Here's what i think:

1. false, since the intersection of 2 context free languages is not necessarily context free since CFLs are not closed under intersection. And if it's not CF then it can't be recursive.

2. false, not sure why tho...just my intuition

3. i wasn't sure what compatible transitions meant.

 

if you know the answers, that would really help me out, and also explain why. Thanks!

[bascule]

1. false, since the intersection of 2 context free languages is not necessarily context free since CFLs are not closed under intersection. And if it's not CF then it can't be recursive.

 

Correct (I believe). As someone who has been taking bits and pieces of two CFLs and trying to put them together in practice I can certainly attest as to the difficulty. It's only possible for the intersection of two CFLs to be a CFL when you do a lot of tedious manual work deciding which conflicting parts of the two languages you want to keep.

 

2. false, not sure why tho...just my intuition

 

I believe this one is true, and more, that you may even be able to express that as a regular language. For example, here's a regular expression that will match strings of even length only:

 

^(..)*$

 

Couldn't you just take the intersection of that with another regular language and get a regular language which matches the description?

 

3. i wasn't sure what compatible transitions meant.

 

I have a vague idea of what the question is asking but have no idea what the answer is?