Register

GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 23

• retagged by
717 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}$.
• retagged by
User Avatar

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
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

535
views
1 answers
7 votes
GO Classes asked Jan 28
535 views
GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 56
For a string $x=x_1 \cdots x_n \in \Sigma^*$, where $\Sigma$ is any alphabet and $x_1, \ldots, x_n \in \Sigma$, we write $x^{\uparrow m}=x^m$ (that is, the usual ... in \Sigma^*\right\}$\left\{(a b c)^{\downarrow n} \mid n \geq 0\right\}$
User Avatar
628
views
1 answers
6 votes
GO Classes asked Jan 28
628 views
GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 24
Let $\mathrm{M}$ be a $8$-state Deterministic Finite Automaton over the alphabet $\{a, b, c\}$. If the language accepted by $\text{M}$ i.e. $\text{L(M)}$ is finite, then the maximum possible cardinality of $\text{L(M)}$ is __________.
User Avatar
443
views
1 answers
4 votes
GO Classes asked Jan 28
443 views
GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 25
A garage door opens if it ever sees the password $011$ in a transmission. More formally, this FSM takes a bitstring consisting of $\text{0's}$ and $\text{1's}$ as its input, and ... $3 - (1/0)$Arrow $4 - (1/0)$Arrow $5 - (1/1)$
User Avatar
482
views
2 answers
3 votes
GO Classes asked Jan 28
482 views
GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 27
What statement is correct for $f(A, B)$ in the following circuit?$f(A, B)=\overline{\overline{A \cdot B} \cdot(A+B)}$ when Control $=1$ ... }$ when Control $=1$f(A, B)=\overline{A} \cdot \overline{B}$ when Control $=0$
User Avatar
Link Copied!