Question

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?

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

Homework Answers

Answer #1

The intersection of a CFL and regular language is always regular and context free.

A language is regular if and only if it is accepted by some NFA, the complement of a regular language is also regular. Languages are sets. Therefore all the properties of sets are inherited by languages.

A context-free grammar (CFG) is a set of recursive rewriting rules used to generate patterns of strings. A CFG consists of the following components: a set of terminal symbols, which are the characters of the alphabet that appear in the strings generated by the grammar.

A regular language satisfies the following equivalent properties: it is the language of a regular expression it is the language accepted by a nondeterministic finite automaton (NFA) it is the language accepted by a deterministic finite automaton (DFA) it can be generated by a regular grammar.

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 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.
Please make a Context Free Grammar (CFG) for the regular languages below: The language that is...
Please make a Context Free Grammar (CFG) for the regular languages below: The language that is in C++ and containing lowercase and upper case letters, and also can have digits, and can also contain the underscore character '_', and it must begin with an underscore or a letter.
La=c^b=d=(a^ib^jc^id^j| i,j>0) using pumping lemma to prove it is not context free language
La=c^b=d=(a^ib^jc^id^j| i,j>0) using pumping lemma to prove it is not context free language
prove that the language L over {c,d,e} is not context free. (using pumping lemma for context...
prove that the language L over {c,d,e} is not context free. (using pumping lemma for context free languages) L= {w ∈ {c,d,e}* : number of c's, number of d's, and number of e's have a common factor greater than 1}
using pumping lemma to prove a^ib^jc^k(i=j or j=k) is not a regular language
using pumping lemma to prove a^ib^jc^k(i=j or j=k) is not a regular language
prove that the language L = {a^n+1 b^2n(aa)^n b | n > 0} is non-context free....
prove that the language L = {a^n+1 b^2n(aa)^n b | n > 0} is non-context free. Using pumping lemma with length
I quit social media for 1 month -- it was the best choice I ever made...
I quit social media for 1 month -- it was the best choice I ever made I quit social media for a month. So, I quit Facebook, Instagram, Snapchat, and Twitter. I just needed a break. It was time to cut myself off I stopped using social media this morning and my brain is going crazy. I just realised how often I glance down just to see if I have a notification. When I wake up in the morning, on...
comment on 2 things you learned from this chapter of the Cognitive development ece 124 chapter...
comment on 2 things you learned from this chapter of the Cognitive development ece 124 chapter 9 Piaget -Preoperational intelligence • Cognitive development between the ages of about 2 and 6 • Includes language and imagination • Suggests logical, operational thinking is not yet possible at this stage Piaget: Symbolic Thought • Major accomplishment of preoperational intelligence • Allows a child to think symbolically, including understanding that words can refer to things not seen and that an item can symbolize...
9. Which of the following is not true about the virtues in Aristotle’s ethics? (a) They...
9. Which of the following is not true about the virtues in Aristotle’s ethics? (a) They are states of character. (b) The virtuous person experiences pleasure when doing virtuous actions. (c) They are acquired via divine commands. (d) They allow our characteristic activities to be performed well. (e) They require our sentiment as well as our intellect.                                                                                                 10. Which of the following best captures the conclusion of Nagel’s argument in “What Is It Like to be a Bat?” (a)...
The Business Case for Agility “The battle is not always to the strongest, nor the race...
The Business Case for Agility “The battle is not always to the strongest, nor the race to the swiftest, but that’s the way to bet ’em!”  —C. Morgan Cofer In This Chapter This chapter discusses the business case for Agility, presenting six benefits for teams and the enterprise. It also describes a financial model that shows why incremental development works. Takeaways Agility is not just about the team. There are product-management, project-management, and technical issues beyond the team’s control. Lean-Agile provides...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT