Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Filter
No answer
No selected answer
No upvoted answer
Previous GATE
Featured
Recent questions without answers
0
votes
0
answers
4411
Ullman (TOC) Edition 3 Exercise 7.1 Question 2 (Page No. 275 - 276 - 277)
Begin with grammar$:$ $S\rightarrow ASB|\in$ $A\rightarrow aAS|a$ $B\rightarrow SbS|A|bb$ Eliminate $\in-$productions. Eliminate any unit productions in the resulting grammar. Eliminate any useless symbols in the resulting grammar. Put the resulting grammar into Chomsky Normal Form.
Begin with grammar$:$$S\rightarrow ASB|\in$$A\rightarrow aAS|a$$B\rightarrow SbS|A|bb$Eliminate $\in-$productions.Eliminate any unit productions in the resulting grammar....
admin
244
views
admin
asked
Apr 11, 2019
Theory of Computation
ullman
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
4412
Allen Carrer Institute: TOC1
How many no. of states in DFA for the following required expression? $(a + b + c) (a + b + c) (a + b + c) (a + b + c) ……… (n – 2)$ times $(a + b + c)^{+}$ $(1) $ $n – 1$ $(2) $ $n$ $(3) $ $n + 1$ $(4) $ $n + 2$ Plz confirm me the answer . Is it $(n-1)$ or $n ?$
How many no. of states in DFA for the following required expression?$(a + b + c) (a + b + c) (a + b + c) (a + b + c) ……… (n – 2)$ times $(a + b + c)^{+}$$(1) $$n ...
srestha
424
views
srestha
asked
Apr 11, 2019
Theory of Computation
finite-automata
+
–
0
votes
0
answers
4413
Kenneth Rosen Edition 7 Exercise 2.3 Question 74 (Page No. 155)
Prove or disprove each of these statements about the floor and ceiling functions. $\left \lfloor \left \lceil x \right \rceil \right \rfloor = \left \lceil x \right \rceil$ for all real numbers $x.$ ... $x$ and $y.$
Prove or disprove each of these statements about the floor and ceiling functions.$\left \lfloor \left \lceil x \right \rceil \right \rfloor = \left \lceil x \right \rceil...
Pooja Khatri
357
views
Pooja Khatri
asked
Apr 11, 2019
Set Theory & Algebra
kenneth-rosen
discrete-mathematics
set-theory&algebra
+
–
0
votes
0
answers
4414
Kenneth Rosen Edition 7 Exercise 2.3 Question 73 (Page No. 155)
Prove or disprove each of these statements about the floor and ceiling functions. $\left \lceil \left \lfloor x \right \rfloor \right \rceil = \left \lfloor x \right \rfloor$ for all real number $x.$ ... $x.$
Prove or disprove each of these statements about the floor and ceiling functions.$\left \lceil \left \lfloor x \right \rfloor \right \rceil = \left \lfloor x \right \rflo...
Pooja Khatri
282
views
Pooja Khatri
asked
Apr 11, 2019
Set Theory & Algebra
kenneth-rosen
discrete-mathematics
set-theory&algebra
+
–
0
votes
0
answers
4415
Kenneth Rosen Edition 7 Exercise 2.3 Question 71 (Page No. 155)
Let $S$ be a subset of a universal set $U$. The characteristic function $f_{s}$ of $S$ is the function from $U$ to the set $\left \{ 0,1 \right \}$ such that $f_{S}(x)=1$ if $x$ belongs to $S$ and $f_S(x)=0$ if $x$ does not belong to $S$. Let $A$ ... $f_{A \oplus B}(x) = f_{A}(x) + f_{B}(x)- 2 f_{A}(x) f_{B}(x) $
Let $S$ be a subset of a universal set $U$. The characteristic function $f_{s}$ of $S$ is the function from $U$ to the set $\left \{ 0,1 \right \}$ such that $f_{S}(x)=1$...
Pooja Khatri
268
views
Pooja Khatri
asked
Apr 11, 2019
Set Theory & Algebra
kenneth-rosen
discrete-mathematics
set-theory&algebra
+
–
0
votes
0
answers
4416
Kenneth Rosen Edition 7 Exercise 2.3 Question 70 (Page No. 155)
Suppose that $f$ is an invertible function from $Y$ to $Z$ and $g$ is an invertible function from $X$ to $Y$. Show that the inverse of the composition $fog$ is given by $(fog)^{-1} = g^{-1} o f^{-1}.$
Suppose that $f$ is an invertible function from $Y$ to $Z$ and $g$ is an invertible function from $X$ to $Y$. Show that the inverse of the composition $fog$ is given by $...
Pooja Khatri
210
views
Pooja Khatri
asked
Apr 11, 2019
Set Theory & Algebra
kenneth-rosen
discrete-mathematics
set-theory&algebra
+
–
0
votes
0
answers
4417
Kenneth Rosen Edition 7 Exercise 2.3 Question 68 (Page No. 155)
Draw graphs of each of these functions. $f(x) =$ $\left \lceil 3x-2 \right \rceil$ $f(x) =$ $\left \lceil 0.2x \right \rceil$ $f(x) =$ $\left \lfloor -1/x \right \rfloor$ $f(x) =$ $\left \lfloor x^2 \right \rfloor$ ... $f(x) =$ $\left \lfloor 2\left \lceil x/2 \right \rceil +1/2\right \rfloor$
Draw graphs of each of these functions.$f(x) =$ $\left \lceil 3x-2 \right \rceil$$f(x) =$ $\left \lceil 0.2x \right \rceil$$f(x) =$ $\left \lfloor -1/x \right \rfloor$$f(...
Pooja Khatri
195
views
Pooja Khatri
asked
Apr 11, 2019
Set Theory & Algebra
kenneth-rosen
discrete-mathematics
set-theory&algebra
+
–
0
votes
0
answers
4418
Kenneth Rosen Edition 7 Exercise 2.3 Question 67 (Page No. 155)
Draw graphs of each of these functions. $f(x) =$ $\left \lfloor x+1/2 \right \rfloor$ $f(x) =$ $\left \lfloor 2x+1 \right \rfloor$ $f(x) =$ $\left \lceil x/3 \right \rceil$ $f(x) =$ $\left \lceil 1/x \right \rceil$ ... $f(x) =$ $\left \lceil \left \lfloor x-12 \right \rfloor + 1/2\right \rceil$
Draw graphs of each of these functions.$f(x) =$ $\left \lfloor x+1/2 \right \rfloor$$f(x) =$ $\left \lfloor 2x+1 \right \rfloor$$f(x) =$ $\left \lceil x/3 \right \rceil$$...
Pooja Khatri
158
views
Pooja Khatri
asked
Apr 11, 2019
Set Theory & Algebra
kenneth-rosen
discrete-mathematics
set-theory&algebra
+
–
0
votes
0
answers
4419
Kenneth Rosen Edition 7 Exercise 2.3 Question 66 (Page No. 155)
Draw the graph of the function $f(n) =$ $\left \lceil x \right \rceil +\left \lceil x/2 \right \rceil$ from $R$ to $R$
Draw the graph of the function $f(n) =$ $\left \lceil x \right \rceil +\left \lceil x/2 \right \rceil$ from $R$ to $R$
Pooja Khatri
170
views
Pooja Khatri
asked
Apr 11, 2019
Set Theory & Algebra
kenneth-rosen
discrete-mathematics
set-theory&algebra
+
–
0
votes
0
answers
4420
Kenneth Rosen Edition 7 Exercise 2.3 Question 65 (Page No. 155)
Draw the graph of the function $f(n) =$\left \lfloor x \right \rfloor +\left \lfloor x/2 \right \rfloor$ from $R$ to $R$
Draw the graph of the function $f(n) =$$\left \lfloor x \right \rfloor +\left \lfloor x/2 \right \rfloor$ from $R$ to $R$
Pooja Khatri
189
views
Pooja Khatri
asked
Apr 11, 2019
Set Theory & Algebra
kenneth-rosen
discrete-mathematics
set-theory&algebra
+
–
0
votes
0
answers
4421
Kenneth Rosen Edition 7 Exercise 2.3 Question 64 (Page No. 155)
Draw the graph of the function $f(n) =$\left \lfloor x/2 \right \rfloor$ from $R$ to $R$
Draw the graph of the function $f(n) =$$\left \lfloor x/2 \right \rfloor$ from $R$ to $R$
Pooja Khatri
157
views
Pooja Khatri
asked
Apr 11, 2019
Set Theory & Algebra
kenneth-rosen
discrete-mathematics
set-theory&algebra
+
–
0
votes
0
answers
4422
Kenneth Rosen Edition 7 Exercise 2.3 Question 63 (Page No. 155)
Draw the graph of the function $f(n) =$\left \lfloor 2x \right \rfloor$ from $R$ to $R$
Draw the graph of the function $f(n) =$$\left \lfloor 2x \right \rfloor$ from $R$ to $R$
Pooja Khatri
165
views
Pooja Khatri
asked
Apr 11, 2019
Set Theory & Algebra
kenneth-rosen
discrete-mathematics
set-theory&algebra
+
–
0
votes
0
answers
4423
Kenneth Rosen Edition 7 Exercise 2.3 Question 62 (Page No. 155)
Draw the graph of the function $f(n) = 1-n^2$ from $Z$ to $Z$
Draw the graph of the function $f(n) = 1-n^2$ from $Z$ to $Z$
Pooja Khatri
162
views
Pooja Khatri
asked
Apr 11, 2019
Set Theory & Algebra
kenneth-rosen
discrete-mathematics
set-theory&algebra
+
–
0
votes
0
answers
4424
Kenneth Rosen Edition 7 Exercise 2.3 Question 61 (Page No. 155)
Data are transmitted over a particular Ethernet network in blocks of $1500$ octets (blocks of $8$ bits). How many blocks are required to transmit the following amounts of data over this Ethernet network? (Note that a byte is a synonym for ... $1.544$ $\text{megabytes}$ of data $45.3$ $\text{megabytes of}$ data
Data are transmitted over a particular Ethernet network in blocks of $1500$ octets (blocks of $8$ bits). How many blocks are required to transmit the following amounts of...
Pooja Khatri
363
views
Pooja Khatri
asked
Apr 11, 2019
Set Theory & Algebra
kenneth-rosen
discrete-mathematics
set-theory&algebra
+
–
0
votes
0
answers
4425
Kenneth Rosen Edition 7 Exercise 2.3 Question 60 (Page No. 155)
How many ATM cells (described in Example 28) can be transmitted in $10$ seconds over a link operating at the following rates? $128$ kilobits per second ($1$ kilobit= $1000$ bits) $300$ kilobits per second $1$ megabit per second ($1$ megabit=$1,000,000$ bits)
How many ATM cells (described in Example 28) can be transmitted in $10$ seconds over a link operating at the following rates?$128$ kilobits per second ($1$ kilobit= $1000...
Pooja Khatri
248
views
Pooja Khatri
asked
Apr 11, 2019
Set Theory & Algebra
kenneth-rosen
discrete-mathematics
set-theory&algebra
+
–
0
votes
0
answers
4426
Kenneth Rosen Edition 7 Exercise 2.3 Question 59 (Page No. 155)
How many bytes are required to encode $n$ bits of data where $n$ equals $7$ $17$ $1001$ $28800$
How many bytes are required to encode $n$ bits of data where $n$ equals$7$$17$$1001$$28800$
Pooja Khatri
179
views
Pooja Khatri
asked
Apr 11, 2019
Set Theory & Algebra
kenneth-rosen
discrete-mathematics
set-theory&algebra
+
–
1
votes
0
answers
4427
Kenneth Rosen Edition 7 Exercise 2.3 Question 58 (Page No. 154)
How many bytes are required to encode $n$ bits of data where $n$ equals $4$ $10$ $500$ $3000$
How many bytes are required to encode $n$ bits of data where $n$ equals$4$$10$$500$$3000$
Pooja Khatri
210
views
Pooja Khatri
asked
Apr 11, 2019
Set Theory & Algebra
kenneth-rosen
discrete-mathematics
set-theory&algebra
+
–
0
votes
0
answers
4428
Kenneth Rosen Edition 7 Exercise 2.3 Question 57 (Page No. 154)
Let $a$ and $b$ be real numbers with $a<b$. Use the floor and / or ceiling functions to express the number of integers $n$ that satisfy the inequality $a<n<b.$
Let $a$ and $b$ be real numbers with $a<b$. Use the floor and / or ceiling functions to express the number of integers $n$ that satisfy the inequality $a<n<b.$
Pooja Khatri
251
views
Pooja Khatri
asked
Apr 11, 2019
Set Theory & Algebra
kenneth-rosen
discrete-mathematics
set-theory&algebra
+
–
0
votes
0
answers
4429
Kenneth Rosen Edition 7 Exercise 2.3 Question 56 (Page No. 154)
Let $a$ and $b$ be real numbers with $a<b$. Use the floor and / or ceiling functions to express the number of integers $n$ that satisfy the inequality $a≤n≤b$.
Let $a$ and $b$ be real numbers with $a<b$. Use the floor and / or ceiling functions to express the number of integers $n$ that satisfy the inequality $a≤n≤b$.
Pooja Khatri
292
views
Pooja Khatri
asked
Apr 11, 2019
Set Theory & Algebra
kenneth-rosen
discrete-mathematics
set-theory&algebra
+
–
0
votes
0
answers
4430
Kenneth Rosen Edition 7 Exercise 2.3 Question 55 (Page No. 154)
The function INT is found on some calculators, where INT$(x)$ = $\left \lfloor x \right \rfloor$ when $x$ nonnegative real number and INT$(x)$ = $\left \lceil x \right \rceil$ when x is a negative real number. Show that this INT function satisfies the identity INT$(-x)$=$-$ INT$(x)$
The function INT is found on some calculators, where INT$(x)$ = $\left \lfloor x \right \rfloor$ when $x$ nonnegative real number and INT$(x)$ = $\left \lceil x \right \r...
Pooja Khatri
238
views
Pooja Khatri
asked
Apr 11, 2019
Set Theory & Algebra
kenneth-rosen
discrete-mathematics
set-theory&algebra
+
–
0
votes
0
answers
4431
Kenneth Rosen Edition 7 Exercise 2.3 Question 54 (Page No. 154)
Prove that if $x$ is a reall number , then $\left \lfloor -x \right \rfloor = - \left \lceil x \right \rceil$ and$\left \lceil -x \right \rceil = -\left \lfloor x \right \rfloor$
Prove that if $x$ is a reall number , then $\left \lfloor -x \right \rfloor = - \left \lceil x \right \rceil$ and$\left \lceil -x \right \rceil = -\left \lfloor x \right ...
Pooja Khatri
159
views
Pooja Khatri
asked
Apr 11, 2019
Set Theory & Algebra
kenneth-rosen
discrete-mathematics
set-theory&algebra
+
–
0
votes
0
answers
4432
Gate counseling
My gate 2019 rank is 2966, score 563, marks 48.67 which colleges I can get with this rank? I belong to unreserved category. Graduation marks 68%.
My gate 2019 rank is 2966, score 563, marks 48.67 which colleges I can get with this rank? I belong to unreserved category. Graduation marks 68%.
Psnjit
524
views
Psnjit
asked
Apr 10, 2019
0
votes
0
answers
4433
Peter Linz Edition 4 Exercise 4.2 Question 15 (Page No. 114)
Describe an algorithm which, when given a regular grammar $G$, can tell us whether or not $L (G) = Σ^*$.
Describe an algorithm which, when given a regular grammar $G$, can tell us whether or not $L (G) = Σ^*$.
Naveen Kumar 3
134
views
Naveen Kumar 3
asked
Apr 10, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
+
–
0
votes
0
answers
4434
Peter Linz Edition 4 Exercise 4.2 Question 13 (Page No. 114)
Show that there exists an algorithm that can determine for every regular language $L$, whether or not $|L| ≥ 5$.
Show that there exists an algorithm that can determine for every regular language $L$, whether or not $|L| ≥ 5$.
Naveen Kumar 3
123
views
Naveen Kumar 3
asked
Apr 10, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
+
–
0
votes
0
answers
4435
Peter Linz Edition 4 Exercise 4.2 Question 12 (Page No. 113)
Let $L$ be any regular language on $Σ =$ {$a, b$}. Show that an algorithm exists for determining if $L$ contains any strings of even length.
Let $L$ be any regular language on $Σ =$ {$a, b$}. Show that an algorithm exists for determining if $L$ contains any strings of even length.
Naveen Kumar 3
176
views
Naveen Kumar 3
asked
Apr 10, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
+
–
0
votes
0
answers
4436
Peter Linz Edition 4 Exercise 4.2 Question 11 (Page No. 113)
The operation $tail (L)$ is defined as $tail(L)=$ {$v:uv∈L,u,v∈Σ^*$}. Show that there is an algorithm for determining whether or not $L = tail (L)$ for any regular $L$.
The operation $tail (L)$ is defined as $tail(L)=$ {$v:uv∈L,u,v∈Σ^*$}.Show that there is an algorithm for determining whether or not $L = tail (L)$ for any regular $L...
Naveen Kumar 3
125
views
Naveen Kumar 3
asked
Apr 10, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
+
–
0
votes
0
answers
4437
Peter Linz Edition 4 Exercise 4.2 Question 10 (Page No. 113)
Show that there is an algorithm to determine if $L = shuffle (L, L)$ for any regular $L$.
Show that there is an algorithm to determine if $L = shuffle (L, L)$ for any regular $L$.
Naveen Kumar 3
168
views
Naveen Kumar 3
asked
Apr 10, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
+
–
0
votes
0
answers
4438
Peter Linz Edition 4 Exercise 4.2 Question 9 (Page No. 113)
Let $L$ be a regular language on $Σ$ and $\widehat{w}$ be any string in $Σ^*$. Find an algorithm to determine if $L$ contains any $w$ such that $\widehat{w}$ is a substring of it, that is, such that $w = u\widehat{w} υ$ with $u,υ ∈Σ^*$ .
Let $L$ be a regular language on $Σ$ and $\widehat{w}$ be any string in $Σ^*$. Find an algorithm to determine if $L$ contains any $w$ such that $\widehat{w}$ is a subst...
Naveen Kumar 3
147
views
Naveen Kumar 3
asked
Apr 10, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
+
–
0
votes
0
answers
4439
Peter Linz Edition 4 Exercise 4.2 Question 8 (Page No. 113)
Exhibit an algorithm that, given any regular language $L$, determines whether or not $L =L^*$.
Exhibit an algorithm that, given any regular language $L$, determines whether or not $L =L^*$.
Naveen Kumar 3
154
views
Naveen Kumar 3
asked
Apr 10, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
+
–
0
votes
0
answers
4440
Peter Linz Edition 4 Exercise 4.2 Question 7 (Page No. 113)
Exhibit an algorithm that, given any three regular languages, $L, L_1, L_2,$ determines whether or not $L = L_1 L_ 2$.
Exhibit an algorithm that, given any three regular languages, $L, L_1, L_2,$ determines whether or not $L = L_1 L_ 2$.
Naveen Kumar 3
108
views
Naveen Kumar 3
asked
Apr 10, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
+
–
Page:
« prev
1
...
143
144
145
146
147
148
149
150
151
152
153
...
590
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register