recategorized by
133 views
0 votes
0 votes

A $\textbf{CFG G}$ satisfies the following properties:

  • The number of non-terminals (variables) in $G$ is $3$.
  • The maximum number of symbols in the right hand side of any production rule is $2$.
  • There is a word $w \in L(G)$ whose length is $20$.

Which of the following $\textbf{MUST}$ be true about $L(G)$:

  1. $L(G)$ is regular.
  2. $L(G)$ is infinite.
  3. $L(G)$ can be accepted by a deterministic Turing machine.
  4. $L(G)$ can be accepted (by empty-stack acceptance condition) by a Nondeterministic pushdown automaton which has only one state.
recategorized by

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
3
0 votes
0 votes
0 answers
4
admin asked Nov 30, 2021
121 views
Kamala tosses $11$ fair coins and Rajani tosses $10$ fair coins. The probability that the number of heads obtained by Kamala is more than the number of tails obtained by ...