in Theory of Computation retagged by
605 views
6 votes
6 votes

Which of the following statements is/are false?

  1. If a context-free grammar $\mathrm{G}$ is in Chomsky's normal form, then $\mathrm{G}$ is not ambiguous.
  2. For every number $n$, the language $\text{L}_n=\left\{0^n 1^n\right\}$ is regular.
  3. If $\mathrm{L}^{\ast }$ is regular then $\mathrm{L}$ is regular.
  4. If there's a $10$-state NFA that accepts $\text{L}$ then there's a $100$-state DFA that accepts $\mathrm{L}$.
in Theory of Computation retagged by
605 views

1 comment

The question was NAT.so how to answer it as a msq?..means how to marks/write ans?.

I typed 3, as 3 of them is correct.
0
0

1 Answer

8 votes
8 votes
Option A:
Does transforming a CFG to Chomsky's normal form make it unambiguous?
The answer is No.

There are inherently ambiguous context-free languages, and like all context-free languages they have grammars in Chomsky's normal form, so transforming a CFG to Chomsky's normal form doesn't necessarily make it unambiguous. For the same reason there is no technique to convert an arbitrary context-free grammar to one which is unambiguous.

Deciding whether a given context-free grammar is ambiguous, or whether a given context-free grammar generates an inherently ambiguous language, is undecidable.

Option B:
For any $n$, it is a finite language with only one string. So, it is regular for every $n$.

Option C:
Take $\text{L}=\left\{a^p \mid p\right.$ is prime $\}$; is non-regular but $\text{L}^*$ is regular.

Option D:
If there's a $10$-state NFA that accepts $\text{L}$ then there's definitely a $1024$-states DFA that accepts $\text{L},$ but cannot say conclude that a $100$ state DFA.
edited by

4 Comments

sir did not understand explanation of option 4
0
0
edited by

@surojit In case this helps –

Consider the language \(\mathrm{L=\{w \ |\ w \in \{0,1\}^* \ and \ the\  \text{ninth-last}\ symbol\ of\ w\ is\ 0\}}\). You can easily construct a \(10\)-state \(\mathrm{NFA}\) accepting \(\mathrm{L}\). From subset construction, you can construct a \(2^{10}\)-state \(\mathrm{DFA}\) accepting \(\mathrm{L}\). But, can you construct any \(\mathrm{DFA}\) with less than \(2^9\)-states accepting \(\mathrm{L}\)? (Hint: Try proving you cannot using the intuition that the \(\mathrm{DFA}\) must remember the last \(9\) symbols of any input string \(\mathrm{w}\); Reference - 'Introduction to Automata Theory, Languages, and Computations' by Hopcroft et al. (\(3\)rd edition), Section - \(2.3.6\), example - \(2.13\), page no. - \(64-65\))

P.S. There is no strict upper bound on the number of state a \(\mathrm{DFA}\) accepting \(\mathrm{L}\) can have, only that it must be some finite number. For example - there exists a \(2^{2^{2^{10}}}\)-state \(\mathrm{DFA}\) accepting \(\mathrm{L}\), most of whose states are unreachable from the start state.

0
0

isn't comparison being used in option b ? @GO Classes

0
0

@Swarnava Bose When language is finite, comparisons doesn't matter. All finite languages are Regular.

0
0
Answer:

Related questions