Aspire Faculty ID #19295 · Topic: UGC NET Computer Science June 2019 (Paper II) · Just now
UGC NET Computer Science June 2019 (Paper II)

How can the decision algorithm be constructed for deciding whether context-free language $L$ is finite?

$(a)$ By constructing redundant CFG $G$ in CNF generating language $L$

$(b)$ By constructing non-redundant CFG $G$ in CNF generating language $L$

$(c)$ By constructing non-redundant CFG $G$ in CNF generating language $L-{\Lambda}$, where $\Lambda$ stands for null

Which of the following is correct?

Solution

To decide whether a context-free language is finite or infinite, we can convert the CFG into a non-redundant CFG in CNF.

Usually, the CNF grammar is considered for $L-{\Lambda}$.

After converting into CNF, we check whether there is any recursive derivation or cycle among variables.

If such a recursive structure exists, then the language is infinite.

If no such recursive structure exists, then the language is finite.

So, the correct construction is given in statement $(c)$.

Previous 10 Questions — UGC NET Computer Science June 2019 (Paper II)

Nearest first
1
Match List-I with List-II: List-I List-II (a) $\overlin…
Topic: UGC NET Computer Science June 2019 (Paper II)
2
How many states are there in a minimum state automata equivalent to regular expression given below? Regular expression …
Topic: UGC NET Computer Science June 2019 (Paper II)
3
Shift-reduce parser consists of:$(a)$ Input buffer $(b)$ Stack $(c)$ Parse table Choose the correct option from those …
Topic: UGC NET Computer Science June 2019 (Paper II)
4
Replacing the expression $4*2.14$ by $8.56$ is known as:
Topic: UGC NET Computer Science June 2019 (Paper II)
5
On translating the expression given below into quadruple representation, how many operations are required?$(ij)+(e+f)(a…
Topic: UGC NET Computer Science June 2019 (Paper II)
6
Which data structure is used by the compiler for managing variables and their attributes?
Topic: UGC NET Computer Science June 2019 (Paper II)
7
Consider the following statements: $S_1$: For any integer $n>1$, $a^{\phi(n)}\equiv 1\ (\text{mod }n)$ for all $a\in…
Topic: UGC NET Computer Science June 2019 (Paper II)
8
Consider the following properties with respect to a flow network $G=(V,E)$ in which a flow is a real-valued function $f…
Topic: UGC NET Computer Science June 2019 (Paper II)
9
Consider the following steps: $S_1$: Characterize the structure of an optimal solution $S_2$: Compute the value of an o…
Topic: UGC NET Computer Science June 2019 (Paper II)
10
Consider the complexity class $CO-NP$ as the set of languages $L$ such that $\overline{L}\in NP$, and the following two…
Topic: UGC NET Computer Science June 2019 (Paper II)

Next 10 Questions — UGC NET Computer Science June 2019 (Paper II)

Ascending by ID
1
Consider the following grammar: $S\to XY$ $X\to YaY\mid a$ $Y\to bbX$ Which of the following statements is/are true abo…
Topic: UGC NET Computer Science June 2019 (Paper II)
2
Which of the following problems is/are decidable problem(s) on Turing machine $M$? $(a)$ $G$ is a CFG with $L(G)=\phi$ …
Topic: UGC NET Computer Science June 2019 (Paper II)
3
for a statement, a language $L\subseteq \Sigma^*$ is recursive if there exists some Turing machine $M$. Which of the fo…
Topic: UGC NET Computer Science June 2019 (Paper II)
4
A fully connected network topology is a topology in which there is a direct link between all pairs of nodes. Given a fu…
Topic: UGC NET Computer Science June 2019 (Paper II)
5
What is the name of the protocol that allows a client to send a broadcast message with its MAC address and receive an I…
Topic: UGC NET Computer Science June 2019 (Paper II)
6
You are designing a link layer protocol for a link with a bandwidth of $1$ Gbps over a fiber link with a length of $800…
Topic: UGC NET Computer Science June 2019 (Paper II)
7
You need $500$ subnets, each with about $100$ usable host addresses per subnet. What network mask will you assign using…
Topic: UGC NET Computer Science June 2019 (Paper II)
8
Consider the following two statements with respect to IPv4 in computer networking: $P$: The loopback IP address is a me…
Topic: UGC NET Computer Science June 2019 (Paper II)
9
In the TCP/IP model, encryption and decryption are functions of the _____ layer.
Topic: UGC NET Computer Science June 2019 (Paper II)
10
Which of the following statements is/are true with regard to various layers in the Internet stack?$P$: At the link laye…
Topic: UGC NET Computer Science June 2019 (Paper II)
Ask Your Question or Put Your Review.

loading...