ZuoTi.Pro
Question

TRUE OR FALSE? (Note: E = belongs to) 1. (a* U b*a*)* = (b U a)*....

TRUE OR FALSE? (Note: E = belongs to)

1. (a* U b*a*)* = (b U a)*.

2. There is an algorithm to decide if the language generated by a CFG is infinite.

3. The language L = {an b m : 0 <= n, 0 <= m, and n + m is even} is not a context-free language.

engineering   Computer-Science   
0 0
Add a comment Improve this question Transcribed image text
Next > < Previous
Sort answers by oldest

Homework Answers

Answer #1

Summary: Discussed the Closure Properties of Regular Languages and solved 1 by using them. In 2, provided algorithm so that there is an algorithm to decide if the language generated by a Context Free Grammar is infinite or finite. The language given in 3 is a Context Free Language. Provided Deterministic Finite Automata (DFA) and Regular Expression (RE) for the given language L.

0 0
Add a comment
Know the answer?
Add Answer to:
TRUE OR FALSE? (Note: E = belongs to) 1. (a* U b*a*)* = (b U a)*....
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. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions

  • TRUE OR FALSE? (Note: E = belongs to) 1. A context-free grammar G is in Chomsky...

    TRUE OR FALSE? (Note: E = belongs to) 1. A context-free grammar G is in Chomsky normal form. Then G is not recursive. 2. Let G be an arbitrary context-free grammar. uAv =>* u'A'v' , where u, v, u' and v' E V* and A E (V - Eps), then L(G) is infinite. 3. {ww : w E {a, b}*} is accepted by some NDPDA with exactly two states

  • true/false 21 Uncountable infinity (for example, the cardinality of the real numbers). No Countable infinity (for...

    true/false 21 Uncountable infinity (for example, the cardinality of the real numbers). No Countable infinity (for example, the cardinality of the integers) ? All strings over the alphabet ?. CFG Context-free Grammar CFL Context-free Language L(G) The language generated by a CFG G. L(M) The language accepted by the automaton M. PDA Pushdown Automaton/Automata ISI The cardinality of set S. For example, I01 -o, and if S is an infinite set, ISI could be No or J1 L <M> L(M)...

  • Say True/False 1. If A is a context-free language that is also non-regular, then A has...

    Say True/False 1. If A is a context-free language that is also non-regular, then A has a CFG in Chomsky normal form. 2. If A ⊆ B and A is a context-free language, then B is a context-free language.

  • If L1 and L2 are Regular Languages, then L1  ∪ L2  is a CFL. Group of answer choices...

    If L1 and L2 are Regular Languages, then L1  ∪ L2  is a CFL. Group of answer choices True False Flag this Question Question 61 pts If L1 and L2 are CFLs, then L1  ∩ L2 and L1 ∪ L2 are CFLs. Group of answer choices True False Flag this Question Question 71 pts The regular expression ((ac*)a*)* = ((aa*)c*)*. Group of answer choices True False Flag this Question Question 81 pts Some context free languages are regular. Group of answer choices True...

  • UueSLIORS! 1. Find the error in logic in the following statement: We know that a b'...

    UueSLIORS! 1. Find the error in logic in the following statement: We know that a b' is a context-free, not regular language. The class of context-free languages are not closed under complement, so its complement is not context free. But we know that its complement is context-free. 2. We have proved that the regular languages are closed under string reversal. Prove here that the context-free languages are closed under string reversal. 3. Part 1: Find an NFA with 3 states...

  • 9. Mark the best description (smallest language class) for each of the following lang • R...

    9. Mark the best description (smallest language class) for each of the following lang • R if it is regular • C if it is context free, but not regular . N if it is "bigger than" context free You do not have to prove your answer. L = {www: we {a,b}"} L2 = {a" : n > 2, m < 5} L3 = {a"m : n + m is even } LA = {w:na(w) + no(w) = n(w)} Ls...

  • Question Completion Status: QUESTION 10 10 points Save Answ Check EXACTLY THOSE claims that are TRUE....

    Question Completion Status: QUESTION 10 10 points Save Answ Check EXACTLY THOSE claims that are TRUE. (Note on notation: for any program say X (where X may be an automaton of any type (as stated), or a grammar, or a regular expression), let L(X) stand for the language defined by X.) There exists an algorithm that operates as follows. INPUT: context free grammar G QUESTION: Is the complement of L(G) regular ? There exists an algorithm that operates as follows....

  • Please also note that there might be multiple answers for each question. Q1: Which of the following claims are true?*...

    Please also note that there might be multiple answers for each question. Q1: Which of the following claims are true?* 1 point The recognizable languages are closed under union and intersection The decidable languages are closed under union and intersection The class of undecidable languages contains the class of recognizable languages For every language A, at least one of A or A*c is recognizable Other: This is a required question Q2: Which of the following languages are recognizable? (Select all...

  • Urgent plz Check EXACTLY THOSE daims that are TRUE. (Note on notation: for any program say...

    Urgent plz Check EXACTLY THOSE daims that are TRUE. (Note on notation: for any program say X(where X may be an automaton of any type (as stated), or a grammar, or a regular expression), let L(X) stand for the language defined by X.) There exists an algorithm that operates as follows. INPUT: Turing machine M that decides set L(M) OUTPUT: Turing machine My that accepts the complement of L(M) by halting There exists an algorithm that operates as follows. INPUT:...

  • For each of the following statements. state whether it is True or False. Prove your answer:...

    For each of the following statements. state whether it is True or False. Prove your answer: a. ∀L1 , L2(L1= L2)iff L1*·=L2*). b. (ØuØ*)n(¬Ø- (ØØ*)) = Ø (where ¬Ø is the complement of Ø). c. Every infinite language is the complement of a finite language. d. ∀L ((LR)R = L). e. ∀L1, L2((L1L2)*= L1*L2*). f. ∀L1, L2(( ((L1*L2*L1*)*= (L2UL1)*). g . ∀L1, L2(( ( ( L 1 U L 2 ) * = L 1 * U L 2 *...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT