Recent questions

0 votes

0 answers

1

Practicing Algorithms and Data Structures for Interview
I have got a good GATE rank in 2019 and most probably I will get into IIT-B TA. I am thinking of working on algorithms and data structures before I join. I have gone through a lot of content regarding ... someone provide some pointers or any resources that help me improve my skills for competitive coding or interview preparation in general?

asked 3 hours ago in Others by gmrishikumar Active (1.8k points) | 6 views

0 votes

0 answers

2

navathe-doubt
previous value of X=9 Sf : w1(X, 5); w2(X, 8); a1; cascadeless schedu;e . what problem will the schedule face??

asked 5 hours ago in Databases by Doraemon (195 points) | 2 views

0 votes

0 answers

3

Made Easy Test Series: Computer Network-ICMP
Consider a very large network $10000$ routers. Two host $A$ and $B$ connected with this network. Host $A$ sends a data to host $B$. and after some unit of time host $A$ receives $ICMP$ time exceed message for the samedata ... some ICMP message generated? Say if $ICMP$ message generated in $9999th$ router, then where it give error of time exceed message?

asked 9 hours ago in Computer Networks by srestha Veteran (111k points) | 8 views

0 votes

0 answers

4

Peter Linz Edition 4 Exercise 7.1 Question 9 (Page No. 183)
Is it possible to find a dfa that accepts the same language as the pda $M= (${$q_0,q_1$},{$a,b$},{$z$},$\delta,q_0,z,${$q_1$}), with $\delta(q_0,a,z)=${$(q_1,z)$}, $\delta(q_0,b,z)=${$(q_0,z)$}, $\delta(q_1,a,z)=${$(q_1,z)$}, $\delta(q_1,b,z)=${$(q_0,z)$} ?

asked 10 hours ago in Theory of Computation by Naveen Kumar 3 Loyal (7.1k points) | 2 views

0 votes

0 answers

5

Peter Linz Edition 4 Exercise 7.1 Question 8 (Page No. 183)
Find an npda for the language $L =$ {$ab (ab)^n b (ba)^n : n ≥ 0$}.

asked 10 hours ago in Theory of Computation by Naveen Kumar 3 Loyal (7.1k points) | 1 view

0 votes

0 answers

6

Peter Linz Edition 4 Exercise 7.1 Question 7 (Page No. 183)
Find an npda for the concatenation of $L (a^*)$ and the language in Exercise 6.

asked 10 hours ago in Theory of Computation by Naveen Kumar 3 Loyal (7.1k points) | 1 view

0 votes

0 answers

7

Peter Linz Edition 4 Exercise 7.1 Question 6 (Page No. 183)
Find an npda on $Σ =$ {$a, b, c$} that accepts the language $L=${$w_1cw_2:w_1,w_2∈$ {$a,b$}$^*,w_1\neq w_2^R$}.

asked 10 hours ago in Theory of Computation by Naveen Kumar 3 Loyal (7.1k points) | 1 view

0 votes

0 answers

8

Peter Linz Edition 4 Exercise 7.1 Question 5 (Page No. 183)
Construct an npda that accepts the language $L =$ {$a^nb^m : n ≥ 0, n ≠ m$}.

asked 10 hours ago in Theory of Computation by Naveen Kumar 3 Loyal (7.1k points) | 1 view

0 votes

0 answers

9

Peter Linz Edition 4 Exercise 7.1 Question 4 (Page No. 183)
Construct npda's that accept the following languages on $Σ =$ {$a, b, c$}. (a) $L =$ {$a^nb^{2n} : n ≥ 0$}. (b) $L =$ {$wcw^R : w ∈$ {$a, b$}$^*$}. (c) $L =$ {$a^nb^mc^{n+m} : n ≥ 0, m ≥ 0$}. (d) $L =$ ... $L =$ {$w : n_a (w) + n_b (w) = n_c (w)$}. (j) here. (k) $L =$ {$w : n_a (w) < n_b (w)$}.

asked 11 hours ago in Theory of Computation by Naveen Kumar 3 Loyal (7.1k points) | 1 view

0 votes

0 answers

10

Peter Linz Edition 4 Exercise 7.1 Question 3 (Page No. 183)
Construct npda's that accept the following regular languages. (a) $L_1 = L (aaa^*b)$. (b) $L_1 = L (aab^*aba^*)$. (c & d here)

asked 11 hours ago in Theory of Computation by Naveen Kumar 3 Loyal (7.1k points) | 3 views

+1 vote

1 answer

11

P and NP Question doubt
What will be the answer to this question? L’ is the complement of language L belongs to NP does not always imply that L’ belongs to NP L’ belongs to P both a and b

asked 11 hours ago in Theory of Computation by Rhythm (133 points) | 52 views

0 votes

0 answers

12

Peter Linz Edition 4 Exercise 7.1 Question 2 (Page No. 183)
Prove that an npda for accepting the language $L =$ { $ww^R : w ∈$ {$a, b$}$^+$ } does not accept any string not in {$ww^R$}.

asked 11 hours ago in Theory of Computation by Naveen Kumar 3 Loyal (7.1k points) | 1 view

0 votes

0 answers

13

P and np question

asked 11 hours ago in Theory of Computation by Rhythm (133 points) | 17 views

0 votes

0 answers

14

Peter Linz Edition 4 Exercise 7.1 Question 1 (Page No. 183)
Find a pda with fewer than four states that accepts the language $L=${$a^nb^n:n\geq 0$} $\cup$ {$a$}.

asked 11 hours ago in Theory of Computation by Naveen Kumar 3 Loyal (7.1k points) | 3 views

0 votes

1 answer

15

Made Easy Test Series : Algorithm
for(k=1;k<(n+1);k++) { for(m=1;m<(n+1);m+=k){ x=x+1; } } What is the T.C. of the following code? Is it $n^{2}$ or $n\log n$??

asked 13 hours ago in Algorithms by srestha Veteran (111k points) | 33 views

0 votes

0 answers

16

Bounded lattice
Can a countable infinite lattice be bounded?

asked 16 hours ago in Set Theory & Algebra by Manoj Kumar Pandey (177 points) | 10 views

0 votes

0 answers

17

Probability of error detection
A block of bits with n rows and m columns uses horizontal and vertical parity bits for error detection. If exactly 4 bits are in error during transmission, derive an expression for the probability that the error will be detected.

asked 17 hours ago in Probability by Priyanka17 Active (1.3k points) | 7 views

0 votes

0 answers

18

IITB direct TA admissions
When does IITb start with the offers of MTech round 1

asked 1 day ago in IISc/IITs by Kartavya Kothari 1 (111 points) | 17 views

0 votes

0 answers

19

Self doubt:Pumping Lemma
How by Pumping Lemma we can prove that “context free grammar generate an infinite number of strings” and here what could be pumping length ?

asked 1 day ago in Theory of Computation by srestha Veteran (111k points) | 3 views

0 votes

0 answers

20

Peter Linz Edition 4 Exercise 6.3 Question 4 (Page No. 173)
Use the CYK method to determine if the string $w = aaabbbbab$ is in the language generated by the grammar $S → aSb|b$.

asked 1 day ago in Theory of Computation by Naveen Kumar 3 Loyal (7.1k points) | 5 views

0 votes

0 answers

21

Peter Linz Edition 4 Exercise 6.3 Question 3 (Page No. 173)
Use the approach employed in Exercise 2 to show how the CYK membership algorithm can be made into a parsing method.

asked 1 day ago in Theory of Computation by Naveen Kumar 3 Loyal (7.1k points) | 3 views

0 votes

0 answers

22

Peter Linz Edition 4 Exercise 6.3 Question 2 (Page No. 173)
Use the CYK algorithm to find a parsing of the string $aab$, using the grammar with productions $S\rightarrow AB,$ $A\rightarrow BB|a,$ $B\rightarrow AB|b.$

asked 1 day ago in Theory of Computation by Naveen Kumar 3 Loyal (7.1k points) | 4 views

0 votes

0 answers

23

Peter Linz Edition 4 Exercise 6.3 Question 1 (Page No. 172)
Use the CYK algorithm to determine whether the strings $aabb, aabba,$ and $abbbb$ are in the language generated by the grammar with productions $S\rightarrow AB,$ $A\rightarrow BB|a,$ $B\rightarrow AB|b.$

asked 1 day ago in Theory of Computation by Naveen Kumar 3 Loyal (7.1k points) | 2 views

0 votes

0 answers

24

Peter Linz Edition 4 Exercise 6.2 Question 16 (Page No. 170)
“Two-standard form is general; for any context-free grammar $G$ with $λ ∉ L (G),$ there exists an equivalent grammar in two-standard form.” Prove this.

asked 1 day ago in Theory of Computation by Naveen Kumar 3 Loyal (7.1k points) | 1 view

0 votes

0 answers

25

Peter Linz Edition 4 Exercise 6.2 Question 15 (Page No. 170)
A context-free grammar is said to be in two-standard form if all production rules satisfy the following pattern $A\rightarrow aBC,$ $A\rightarrow aB,$ $A\rightarrow a,$ where $A, B, C ∈ V$ and $a ∈ T$. Convert the grammar ... $S\rightarrow aSA,$ $A\rightarrow bABC,$ $B\rightarrow b,$ $C\rightarrow aBC$ into two-standard form.

asked 1 day ago in Theory of Computation by Naveen Kumar 3 Loyal (7.1k points) | 1 view

0 votes

0 answers

26

Peter Linz Edition 4 Exercise 6.2 Question 14 (Page No. 170)
Can every linear grammar be converted to a form in which all productions look like $A → ax,$ where $a∈ T$ and $x∈V$ $\cup$ {$\lambda$} ?

asked 1 day ago in Theory of Computation by Naveen Kumar 3 Loyal (7.1k points) | 2 views

0 votes

0 answers

27

Peter Linz Edition 4 Exercise 6.2 Question 13 (Page No. 170)
Convert the grammar $S\rightarrow ABb|a,$ $A\rightarrow aaA|B,$ $B\rightarrow bAb$ into Greibach normal form.

asked 1 day ago in Theory of Computation by Naveen Kumar 3 Loyal (7.1k points) | 1 view

0 votes

0 answers

28

Peter Linz Edition 4 Exercise 6.2 Question 12 (Page No. 170)
Convert the grammar $S\rightarrow ab|aS|aaS$ into Greibach normal form.

asked 1 day ago in Theory of Computation by Naveen Kumar 3 Loyal (7.1k points) | 1 view

0 votes

0 answers

29

Peter Linz Edition 4 Exercise 6.2 Question 11 (Page No. 170)
Convert the following grammar into Greibach normal form. $S\rightarrow aSb|ab$

asked 1 day ago in Theory of Computation by Naveen Kumar 3 Loyal (7.1k points) | 1 view

0 votes

0 answers

30

Peter Linz Edition 4 Exercise 6.2 Question 10 (Page No. 170)
Convert the grammar $S\rightarrow aSb|bSa|a|b$ into Greibach normal form.

asked 1 day ago in Theory of Computation by Naveen Kumar 3 Loyal (7.1k points) | 1 view

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true

Recent Posts

Recent Blog Comments