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

Consider the following statements with respect to the language $L={a^n b^n\mid n\ge 0}$

$S_1:L^2$ is context free language

$S_2:L^k$ is context-free language for any given $k\ge 1$

$S_3:\overline{L}$ and $L^*$ are context free languages

Which one of the following is correct?

Solution

Given language:

$L={a^n b^n\mid n\ge 0}$

This is a context free language.

Now check each statement.

For $S_1$:

$L^2=L\cdot L$

Context free languages are closed under concatenation.

So, $L^2$ is also context free.

Hence, $S_1$ is true.

For $S_2$:

$L^k$ means concatenation of $L$ with itself $k$ times.

For any fixed $k\ge 1$, context free languages are closed under finite concatenation.

So, $L^k$ is context free.

Hence, $S_2$ is true.

For $S_3$:

$L^*$ is context free because context free languages are closed under Kleene star.

Also, for this specific language $L={a^n b^n\mid n\ge 0}$, its complement $\overline{L}$ is also context free.

So, $\overline{L}$ and $L^*$ both are context free languages.

Hence, $S_3$ is true.

Therefore, all three statements $S_1,\ S_2$ and $S_3$ are correct.

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

Nearest first
1
Consider $\Sigma={w,x}$ and $T={x,y,z}$. Define homomorphism $h$ by: $h(x)=xzy$ $h(w)=zxyy$ If $L$ is the regular langu…
Topic: UGC NET Computer Science Dec 2019 (Paper II)
2
Consider the following grammar: $S\rightarrow 0A\mid 0BB$ $A\rightarrow 00A\mid \lambda$ $B\rightarrow 1B\mid 11C$ $C\r…
Topic: UGC NET Computer Science Dec 2019 (Paper II)
3
Consider the language $L={a^n b^{n-3}\mid n>2}$ on $\Sigma={a,b}$. Which one of the following grammars generates the…
Topic: UGC NET Computer Science Dec 2019 (Paper II)
4
 Consider the following grammars: $G_1:S\rightarrow aSb\mid bSa\mid aa$ $G_2:S\rightarrow aSb\mid bSa\mid SS\mid \…
Topic: UGC NET Computer Science Dec 2019 (Paper II)
5
The time complexity to multiply two polynomials of degree $n$ using Fast Fourier transform method is:
Topic: UGC NET Computer Science Dec 2019 (Paper II)
6
When using Dijkstra's algorithm to find shortest path in a graph, which of the following statement is not true?
Topic: UGC NET Computer Science Dec 2019 (Paper II)
7
Consider a weighted directed graph. The current shortest distance from source $S$ to node $x$ is represented by $d[x]$.…
Topic: UGC NET Computer Science Dec 2019 (Paper II)
8
Give asymptotic upper and lower bound for $T(n)$ given below. Assume $T(n)$ is constant for $n\le 2$. $T(n)=4T(\sqrt n)…
Topic: UGC NET Computer Science Dec 2019 (Paper II)
9
In a B-Tree, each node represents a disk block. Suppose one block holds $8192$ bytes. Each key uses $32$ bytes. In a B-…
Topic: UGC NET Computer Science Dec 2019 (Paper II)
10
What is the worst case running time of Insert and Extract-min, in an implementation of a priority queue using an unsort…
Topic: UGC NET Computer Science Dec 2019 (Paper II)

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

Ascending by ID
1
Consider the following languages: $L_1={a^n b^n c^m}\cup{a^n b^m c^m},\ n,m\ge 0$ $L_2={ww^R\mid w\in{a,b}^*}$ where $R…
Topic: UGC NET Computer Science Dec 2019 (Paper II)
2
Let $G=(V,T,S,P)$ be any context-free grammar without any $\lambda$-productions or unit productions. Let $K$ be the max…
Topic: UGC NET Computer Science Dec 2019 (Paper II)
3
 Consider the following language families: $L_1\equiv$ The context-free languages $L_2\equiv$ The context-sensitiv…
Topic: UGC NET Computer Science Dec 2019 (Paper II)
4
Consider the following statements: $S_1:$ There exists no algorithm for deciding if any two Turing machines $M_1$ and $…
Topic: UGC NET Computer Science Dec 2019 (Paper II)
5
 Let $A={001,0011,11,101}$ and $B={01,111,111,010}$. Similarly, let $C={00,001,1000}$ and $D={0,11,011}$. Which of…
Topic: UGC NET Computer Science Dec 2019 (Paper II)
6
Which of the following class of IP address has the last address as $223.255.255.255$?
Topic: UGC NET Computer Science Dec 2019 (Paper II)
7
Consider a subnet with $720$ routers. If a three-level hierarchy is chosen, with eight clusters, each containing $9$ re…
Topic: UGC NET Computer Science Dec 2019 (Paper II)
8
Piconet is a basic unit of a bluetooth system consisting of $...............$ master node and up to $...............$ a…
Topic: UGC NET Computer Science Dec 2019 (Paper II)
9
A network with bandwidth of $10$ Mbps can pass only an average of $12000$ frames per minute with each frame carrying an…
Topic: UGC NET Computer Science Dec 2019 (Paper II)
10
 The full form of ICANN is:
Topic: UGC NET Computer Science Dec 2019 (Paper II)
Ask Your Question or Put Your Review.

loading...