Aspire Faculty ID #18847 · Topic: UGC NET Computer Science Nov 2021 (Paper II) · Just now
UGC NET Computer Science Nov 2021 (Paper II)

 What language is accepted by the pushdown automaton

$M=({q_0,q_1,q_2},\{a,b\},\{a,b,z\},\delta,q_0,z,\{q_2\})$

with

$\delta(q_0,a,a)=\{(q_0,aa)\}$

$\delta(q_0,b,a)=\{(q_0,ba)\}$

$\delta(q_0,a,b)=\{(q_0,ab)\}$

$\delta(q_0,b,b)=\{(q_0,bb)\}$

$\delta(q_0,a,z)=\{(q_0,az)\}$

$\delta(q_0,b,z)=\{(q_0,bz)\}$

$\delta(q_0,\lambda,b)=\{(q_1,b)\}$

$\delta(q_0,\lambda,a)=\{(q_1,a)\}$

$\delta(q_1,a,a)=\{(q_1,\lambda)\}$

$\delta(q_1,b,b)=\{(q_1,\lambda)\}$

$\delta(q_1,\lambda,z)=\{(q_2,z)\}$

Solution

In state $q_0$, the PDA reads input symbols and pushes them into the stack.

So, first part of the string is stored in stack.

After that, using $\lambda$ move, PDA goes from $q_0$ to $q_1$.

In state $q_1$, the PDA reads input and matches it with the top of stack.

If input is $a$ and stack top is $a$, it pops $a$.

If input is $b$ and stack top is $b$, it pops $b$.

So, second part of the string must be reverse of the first part.

When stack reaches bottom symbol $z$, PDA goes to final state $q_2$.

Therefore, language accepted is even length palindrome over $\{a,b\}$.

So,

$L=\{ww^R\mid w\in\{a,b\}^+\}$

Previous 10 Questions — UGC NET Computer Science Nov 2021 (Paper II)

Nearest first
1
Find the regular expression for the language accepted by the automata given below.
Topic: UGC NET Computer Science Nov 2021 (Paper II)
2
What is the minimum number of states required to the finite automaton equivalent to the transition diagram given below?
Topic: UGC NET Computer Science Nov 2021 (Paper II)
3
Given below are two statementsStatement I: The family of context free languages is closed under homomorphism.Statement …
Topic: UGC NET Computer Science Nov 2021 (Paper II)
4
Let$L_1=\{0^n1^n0^m\mid n\ge 1,\ m\ge 1\}$$L_2=\{0^n1^m0^m\mid n\ge 1,\ m\ge 1\}$$L_3=\{0^n1^n0^n\mid n\ge 1\}$Which of…
Topic: UGC NET Computer Science Nov 2021 (Paper II)
5
Any string of terminals that can be generated by the following context-free grammar, where $S$ is start nonterminal sym…
Topic: UGC NET Computer Science Nov 2021 (Paper II)
6
Which of the following languages are not regular?A. $L=\{(01)^n0^k\mid n>k,\ k\ge 0\}$B. $L=\{c^nb^ka^{n+k}\mid n\ge…
Topic: UGC NET Computer Science Nov 2021 (Paper II)
7
Consider the following linear optimization problem:Maximize $Z=6x+5y$Subject to $2x-3y\le 5$$x+3y\le 11$$4x+y\le 15$and…
Topic: UGC NET Computer Science Nov 2021 (Paper II)
8
Let $(X,*)$ be a semigroup. Furthermore, for every $a$ and $b$ in $X$, if $a\ne b$, then $a*b\ne b*a$.Based on the defi…
Topic: UGC NET Computer Science Nov 2021 (Paper II)
9
Match List I with List IIList IList IIA. $x+x=x$I. Identity LawB. $x+0=x$II. Absorption LawC. $x+1=1$III. Idempotent La…
Topic: UGC NET Computer Science Nov 2021 (Paper II)
10
Which of the following Graphs is(are) planar?
Topic: UGC NET Computer Science Nov 2021 (Paper II)

Next 10 Questions — UGC NET Computer Science Nov 2021 (Paper II)

Ascending by ID
1
Match List I with List IIList IList IIA. $S\to XY,\ X\to 0,\ Y\to 1$I. Greibach Normal FormB. $S\to aS\mid bSS\mid c$II…
Topic: UGC NET Computer Science Nov 2021 (Paper II)
2
Which of the following concepts can be used to identify loops?A. Depth first orderingB. DominatorsC. Reducible graphsCh…
Topic: UGC NET Computer Science Nov 2021 (Paper II)
3
Given below are two statementsStatement I: LL(1) and LR are examples of Bottom-up parsers.Statement II: Recursive desce…
Topic: UGC NET Computer Science Nov 2021 (Paper II)
4
The postfix form of the expression $(A+B)*(C*D-E)*F/G$ is ______
Topic: UGC NET Computer Science Nov 2021 (Paper II)
5
A double-ended queue (deque) supports adding and removing items from both ends of the queue. The operations supported b…
Topic: UGC NET Computer Science Nov 2021 (Paper II)
6
Two balanced binary trees are given with $m$ and $n$ elements, respectively. They can be merged into a balanced binary …
Topic: UGC NET Computer Science Nov 2021 (Paper II)
7
A data structure is required for storing a set of integers such that each of the following operations can be done in $O…
Topic: UGC NET Computer Science Nov 2021 (Paper II)
8
Consider the following graph.Among the following sequencesI. $a\ b\ e\ g\ h\ f$II. $a\ b\ f\ e\ h\ g$III. $a\ b\ f\ h\ …
Topic: UGC NET Computer Science Nov 2021 (Paper II)
9
Given below are two statementsStatement I: In an undirected graph, number of odd degree vertices is even.Statement II: …
Topic: UGC NET Computer Science Nov 2021 (Paper II)
10
 Which of the given options provides the increasing order of asymptotic complexity of functions $f_1,\ f_2,\ f_3$ …
Topic: UGC NET Computer Science Nov 2021 (Paper II)
Ask Your Question or Put Your Review.

loading...