Register

Automata Theory by HMU

319 views
0 votes
0 votes
Is L(G) finite, for a given CFG G.

Is decidable or undecidable?
User Avatar

1 Answer

0 votes
0 votes
Yes It is decidable . The finiteness of Context free grammar is decidable

Refrence: chapter 8 Theorem 8.7 Peter Linz text book
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
0 answers
1
wa_tle asked Feb 27, 2022
294 views
INTRODUCTION TO Automata Theory, Languages, and Computation by JOHN E. HOPCROFT
Design e - NF A for accepting decimal numbers
Design e - NF A for accepting decimal numbers
User Avatar
0 votes
0 votes
0 answers
2
Phantom5 asked Sep 3, 2018
865 views
Intro to Automata theory by Ullman Exercise 2nd
Exercise 2.2.8: Let A be a DFA and a particular input symbol of A, such that for all states q of A we have delta(q,a) = q. A) Show that for all n >= 0, Delta cap(q, a^n) = q. where a^n is the string consisting of n a's. note delta = δ and delta cap = δˆ.
Exercise 2.2.8: Let A be a DFA and a particular input symbol of A, such that for all states q of A we have delta(q,a) = q.A) Show that for all n >= 0, Delta cap(q, a^n) ...
User Avatar
1 votes
1 votes
0 answers
3
hashir inayat asked Jul 17, 2017
966 views
introduction to computer theory by daniel cohen 2nd edition Chapter#05 Finite automata question 12
Suppose a particular FA, called FIN, has the property that it had only one final state that was not the start state. During the night, vandals come and switch the + sign ...
User Avatar
0 votes
0 votes
0 answers
4
Ashish RajAnand asked Nov 22, 2018
351 views
formal language and automata by peter linz chapter 1.2 exercise 7
User Avatar
Link Copied!