Question

Prove that the language A\B = {w: wx ∈ A, X ∈ B}, where A is...

Prove that the language A\B = {w: wx ∈ A, X ∈ B}, where A is a CFL and B is regular is a CFL.

Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

The given language is a standard Quotient operation. For clarity, consider the following example to understand the operation before proceeding to the proof:

  • Since A is a CFL and B is a Regular language, A\B is CFL as context free languages are closed under Quotient operation with Regular languages.
  • Proof can be given as:

  • B is a part of wx ,as x∊B And wx∊A

  • Now, L\R (or A\B or wx\x)=CFL/Regular
  • let CFL =anbn  and Regular= b4
  • So, L\R= anbn-4 which is also CFL
  • Hence, A\B is CFL
  • Thus, proved.
0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Use pumping lemma to prove that the language {anb2n| n>0, and w is in {a, b}*...
Use pumping lemma to prove that the language {anb2n| n>0, and w is in {a, b}* } is not a regular language.
5 A Non-Regular language Prove that the language}L={www∣w∈{0,1}​∗​​} is not regular.
5 A Non-Regular language Prove that the language}L={www∣w∈{0,1}​∗​​} is not regular.
Prove that the intersection of a CFL and a Regular language is always context free. I...
Prove that the intersection of a CFL and a Regular language is always context free. I was thinking representing the CFL as a PDA, and the regular language as a DFA, then - if they both accept at the same time, the intersection must be context free?
Let Σ = {0,1}. Prove that the language { w | w contains the substring 01001...
Let Σ = {0,1}. Prove that the language { w | w contains the substring 01001 } is regular by providing a finite automaton to recognize the language. Include a state diagram, formal description, and informal justification for the correctness of your automaton.
Use CFG or PDA to prove L= {0a1b0c : b ≠ a + c; a, b,...
Use CFG or PDA to prove L= {0a1b0c : b ≠ a + c; a, b, c ≥ _0} is a context-free language. Please add your explanation, thank you. If you can use the theorem(union of CFL and regular language = CFL) is also welcomed.
Suppose A and B are regular language. Prove that AB is regular.
Suppose A and B are regular language. Prove that AB is regular.
Are the following languages over {a, b} regular? If they are then prove it. If they...
Are the following languages over {a, b} regular? If they are then prove it. If they are not prove it with the Pumping Lemma {an bm | m != n, n >= 0} {w | w contains the substring ‘aaa’ once and only once } Clear concise details please, if the language is regular, provide a DFA/NFA along with the regular expression. Thank you. Will +1
prove that any regular language L can be represented by a regular expression in DNF(a1Ua2U...Uan), where...
prove that any regular language L can be represented by a regular expression in DNF(a1Ua2U...Uan), where none of ai, 1<=i<=n, contains the operator U.
Prove that the language ?={?^??^??^?:?≤?+?}is not regular
Prove that the language ?={?^??^??^?:?≤?+?}is not regular
Prove the language of strings over {a, b} of the form (b^m)(a^n) , 0 ≤ m...
Prove the language of strings over {a, b} of the form (b^m)(a^n) , 0 ≤ m < n-2 isn’t regular. Use the pumping lemma for regular languages.
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT