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
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 the language ?={?^??^??^?:?≤?+?}is not regular
Prove that the language ?={?^??^??^?:?≤?+?}is not regular
{wRwwR | w ∈{a,b}∗}. prove whether it's regular or not, if it is, draw a DFSM
{wRwwR | w ∈{a,b}∗}. prove whether it's regular or not, if it is, draw a DFSM
For Automata class: Let L be a regular language over the binary alphabet. Consider the following...
For Automata class: Let L be a regular language over the binary alphabet. Consider the following language over the same alphabet: L' = {w | |w| = |u| for some u ∈ L}. Prove that L' is regular.
a.) Simplify f(w, x, y) = (wx + y')(w' + x' + y). You need to...
a.) Simplify f(w, x, y) = (wx + y')(w' + x' + y). You need to show step-by-steps to your final answer.
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT