Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged peter-linz-edition4
0
votes
0
answers
211
Peter Linz Edition 4 Exercise 3.3 Question 13 (Page No. 97)
Find regular grammars for the following languages on {$ a, b$}. (a) $L=${$w:n_a(w)$ and $n_b(w)$ are both even}. (b) $L=${$w:(n_a(w)$ - $n_b(w))$ mod $3=1$}. (c) $L=${$w:(n_a(w)$ - $n_b(w))$ mod $3\neq1$}. (d) $L=${$w:(n_a(w)$ - $n_b(w))$ mod $3\neq0$}. (e) $L=${$w:|n_a(w)$ - $n_b(w)|$ is odd}.
Find regular grammars for the following languages on {$ a, b$}. (a) $L=${$w:n_a(w)$ and $n_b(w)$ are both even}. (b) $L=${$w:(n_a(w)$ - $n_b(w))$ mod $3=1$}. (c) $L=${$w:...
Naveen Kumar 3
229
views
Naveen Kumar 3
asked
Apr 3, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-grammar
+
–
0
votes
0
answers
212
Peter Linz Edition 4 Exercise 3.3 Question 12 (Page No. 97)
Find a regular grammar that generates the language $L=$ {$w∈$ {$a,b$}$^*:n_a(w)+3n_b(w)$ is even } .
Find a regular grammar that generates the language $L=$ {$w∈$ {$a,b$}$^*:n_a(w)+3n_b(w)$ is even } .
Naveen Kumar 3
167
views
Naveen Kumar 3
asked
Apr 3, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-grammar
+
–
0
votes
0
answers
213
Peter Linz Edition 4 Exercise 3.3 Question 11 (Page No. 97)
Find a regular grammar for the language $L =$ {$a^nb^m : n + m$ is even}.
Find a regular grammar for the language $L =$ {$a^nb^m : n + m$ is even}.
Naveen Kumar 3
175
views
Naveen Kumar 3
asked
Apr 3, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-grammar
+
–
0
votes
0
answers
214
Peter Linz Edition 4 Exercise 3.3 Question 10 (Page No. 97)
Find a left-linear grammar for the language $L ((aab^*ab)^*).$
Find a left-linear grammar for the language $L ((aab^*ab)^*).$
Naveen Kumar 3
158
views
Naveen Kumar 3
asked
Apr 3, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-grammar
+
–
0
votes
0
answers
215
Peter Linz Edition 4 Exercise 3.3 Question 7 (Page No. 97)
Find a regular grammar that generates the language on $Σ =$ {$a, b$} consisting of all strings with no more than three $a$'s.
Find a regular grammar that generates the language on $Σ =$ {$a, b$} consisting of all strings with nomore than three $a$'s.
Naveen Kumar 3
168
views
Naveen Kumar 3
asked
Apr 3, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-grammar
+
–
0
votes
1
answer
216
Peter Linz Edition 4 Exercise 3.3 Question 5 (Page No. 96)
Find a left-linear grammar for the language accepted by the nfa below.
Find a left-linear grammar for the language accepted bythe nfa below.
Naveen Kumar 3
503
views
Naveen Kumar 3
asked
Apr 3, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-grammar
+
–
0
votes
0
answers
217
Peter Linz Edition 4 Exercise 3.3 Question 4 (Page No. 96)
Construct right- and left-linear grammars for the language $L =$ {$a^nb^m : n ≥ 2, m ≥ 3$}.
Construct right- and left-linear grammars for the language$L =$ {$a^nb^m : n ≥ 2, m ≥ 3$}.
Naveen Kumar 3
207
views
Naveen Kumar 3
asked
Apr 3, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-grammar
+
–
0
votes
0
answers
218
Peter Linz Edition 4 Exercise 3.3 Question 3 (Page No. 96)
Construct a left-linear grammar for the language generated by the grammar $S → abA,$ $A → baB,$ $B → aA|bb.$
Construct a left-linear grammar for the language generated by the grammar$S → abA,$$A → baB,$$B → aA|bb.$
Naveen Kumar 3
198
views
Naveen Kumar 3
asked
Apr 3, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-grammar
+
–
0
votes
0
answers
219
Peter Linz Edition 4 Exercise 3.3 Question 2 (Page No. 96)
Find a regular grammar that generates the language $L (aa^* (ab+ a)^*)$ .
Find a regular grammar that generates the language $L (aa^* (ab+ a)^*)$ .
Naveen Kumar 3
203
views
Naveen Kumar 3
asked
Apr 3, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-grammar
+
–
0
votes
0
answers
220
Peter Linz Edition 4 Exercise 3.3 Question 1 (Page No. 96)
Construct a dfa that accepts the language generated by the grammar $S → abA, A → baB, B → aA|bb$ .
Construct a dfa that accepts the language generated by the grammar$S → abA,A → baB,B → aA|bb$ .
Naveen Kumar 3
220
views
Naveen Kumar 3
asked
Apr 3, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-grammar
+
–
0
votes
0
answers
221
Peter Linz Edition 4 Exercise 3.2 Question 18 (Page No. 89)
Find nfa's for $L (aØ)$ and $L (Ø^*)$. Is the result consistent with the definition of these languages?
Find nfa's for $L (aØ)$ and $L (Ø^*)$. Is the result consistent with the definition of these languages?
Naveen Kumar 3
189
views
Naveen Kumar 3
asked
Apr 3, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
finite-automata
+
–
1
votes
0
answers
222
Peter Linz Edition 4 Exercise 3.2 Question 17 (Page No. 89)
Analogous to the previous exercise, consider all words that can be formed from $L$ by dropping a single symbol of the string. Formally define this operation drop for languages. Construct an nfa for $drop (L)$, given an nfa for $L$.
Analogous to the previous exercise, consider all words that can be formed from $L$ by droppinga single symbol of the string. Formally define this operation drop for langu...
Naveen Kumar 3
300
views
Naveen Kumar 3
asked
Apr 3, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-expression
regular-language
+
–
0
votes
0
answers
223
Peter Linz Edition 4 Exercise 3.2 Question 16 (Page No. 89)
In some applications, such as programs that check spelling, we may not need an exact match of the pattern, only an approximate one. Once the notion of an approximate match has been made precise, automata theory can be applied to ... this to write a pattern-recognition program for $insert (L)$, using as input a regular expression for $L$.
In some applications, such as programs that check spelling, we may not need an exact match ofthe pattern, only an approximate one. Once the notion of an approximate match...
Naveen Kumar 3
333
views
Naveen Kumar 3
asked
Apr 3, 2019
Theory of Computation
theory-of-computation
peter-linz
peter-linz-edition4
regular-expression
+
–
0
votes
0
answers
224
Peter Linz Edition 4 Exercise 3.2 Question 15 (Page No. 89)
Write a regular expression for the set of all $C$ real numbers.
Write a regular expression for the set of all $C$ real numbers.
Naveen Kumar 3
178
views
Naveen Kumar 3
asked
Apr 3, 2019
Theory of Computation
theory-of-computation
peter-linz
peter-linz-edition4
regular-expression
+
–
0
votes
2
answers
225
Peter Linz Edition 4 Exercise 3.2 Question 13 (Page No. 88)
Find a regular expression for the following languages on {$a, b$}. (a) $L =$ {$w : n_a (w)$ and $n_b (w)$ are both even}. (b) $L =$ {$w :(n_a (w) - n_b (w))$ mod $3 = 1$}. (c) $L =$ {$w :(n_a (w) - n_b (w))$ mod $3 = 0$}. (d) $L =$ {$w :2n_a (w)+3n_b (w)$ is even}.
Find a regular expression for the following languages on {$a, b$}.(a) $L =$ {$w : n_a (w)$ and $n_b (w)$ are both even}.(b) $L =$ {$w :(n_a (w) - n_b (w))$ mod $3 = 1$}.(...
Naveen Kumar 3
557
views
Naveen Kumar 3
asked
Apr 3, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
regular-expression
+
–
2
votes
1
answer
226
Peter Linz Edition 4 Exercise 3.2 Question 10 (Page No. 88)
Find regular expressions for the languages accepted by the following automata:- https://gateoverflow.in/304714/peter-linz-edition-4-exercise-3-2-question-10-b-page-no-88
Find regular expressions for the languages accepted by the following automata:-https://gateoverflow.in/304714/peter-linz-edition-4-exercise-3-2-question-10-b-page-no-88
Naveen Kumar 3
1.4k
views
Naveen Kumar 3
asked
Apr 2, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-expression
regular-language
+
–
0
votes
1
answer
227
Peter Linz Edition 4 Exercise 3.2 Question 9 (Page No. 88)
What language is accepted by the following generalized transition graph?
What language is accepted by the following generalized transition graph?
Naveen Kumar 3
662
views
Naveen Kumar 3
asked
Apr 2, 2019
Theory of Computation
theory-of-computation
peter-linz
peter-linz-edition4
regular-language
regular-expression
+
–
1
votes
0
answers
228
Peter Linz Edition 4 Exercise 3.2 Question 8 (Page No. 87)
Consider the following generalized transition graph. (a) Find an equivalent generalized transition graph with only two states. (b) What is the language accepted by this graph?
Consider the following generalized transition graph.(a) Find an equivalent generalized transition graph with only two states.(b) What is the language accepted by this gra...
Naveen Kumar 3
745
views
Naveen Kumar 3
asked
Apr 2, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-expression
regular-language
+
–
0
votes
0
answers
229
Peter Linz Edition 4 Exercise 3.2 Question 7 (Page No. 87)
Find the minimal dfa that accepts $L(a^*bb) ∪ L(ab^*ba)$.
Find the minimal dfa that accepts $L(a^*bb) ∪ L(ab^*ba)$.
Naveen Kumar 3
160
views
Naveen Kumar 3
asked
Apr 2, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
regular-expression
+
–
1
votes
0
answers
230
Peter Linz Edition 4 Exercise 3.2 Question 6 (Page No. 87)
Find an nfa for all strings not containing the substring 101. Use this to derive a regular expression for that language.
Find an nfa for all strings not containing the substring 101. Use this to derive a regular expression for that language.
Naveen Kumar 3
227
views
Naveen Kumar 3
asked
Apr 2, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
regular-expression
+
–
0
votes
1
answer
231
Peter Linz Edition 4 Exercise 3.2 Question 5 (Page No. 87)
Find dfa's that accept the following languages. (a) $L = L (ab^*a^*)∪ L ((ab)^* ba)$. (b) $L = L (ab^*a^*) $ $\cap$ $L ((ab)^* ba)$.
Find dfa's that accept the following languages.(a) $L = L (ab^*a^*)∪ L ((ab)^* ba)$.(b) $L = L (ab^*a^*) $ $\cap$ $L ((ab)^* ba)$.
Naveen Kumar 3
311
views
Naveen Kumar 3
asked
Apr 2, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
regular-expression
+
–
0
votes
0
answers
232
Peter Linz Edition 4 Exercise 3.2 Question 4 (Page No. 87)
Find dfa's that accept the following languages. (a) $L (aa^* + aba^*b^*)$. (b) $L (ab (a + ab)^* (a + aa))$. (c) $L ((abab)^* + (aaa^* + b)^*)$. (d) $L (((aa^*)^* b)^*)$.
Find dfa's that accept the following languages.(a) $L (aa^* + aba^*b^*)$.(b) $L (ab (a + ab)^* (a + aa))$.(c) $L ((abab)^* + (aaa^* + b)^*)$.(d) $L (((aa^*)^* b)^*)$.
Naveen Kumar 3
245
views
Naveen Kumar 3
asked
Apr 2, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-expression
regular-language
+
–
0
votes
0
answers
233
Peter Linz Edition 4 Exercise 3.2 Question 3 (Page No. 87)
Give an nfa that accepts the language $L((a + b)^* b(a + bb)^*)$.
Give an nfa that accepts the language $L((a + b)^* b(a + bb)^*)$.
Naveen Kumar 3
221
views
Naveen Kumar 3
asked
Apr 2, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-expression
regular-language
+
–
0
votes
0
answers
234
Peter Linz Edition 4 Exercise 3.2 Question 2 (Page No. 87)
Find an nfa that accepts the complement of the language in $L (ab^*aa + bba^*ab)$.
Find an nfa that accepts the complement of the language in $L (ab^*aa + bba^*ab)$.
Naveen Kumar 3
137
views
Naveen Kumar 3
asked
Apr 2, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-expression
regular-language
+
–
0
votes
1
answer
235
Peter Linz Edition 4 Exercise 3.2 Question 1 (Page No. 87)
Find an nfa that accepts the language $L (ab^*aa + bba^*ab)$.
Find an nfa that accepts the language $L (ab^*aa + bba^*ab)$.
Naveen Kumar 3
180
views
Naveen Kumar 3
asked
Apr 2, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-expression
regular-language
+
–
0
votes
1
answer
236
Peter Linz Edition 4 Exercise 3.1 Question 26 (Page No. 77)
Find an nfa that accepts the language $L (aa^* (a + b))$.
Find an nfa that accepts the language $L (aa^* (a + b))$.
Naveen Kumar 3
283
views
Naveen Kumar 3
asked
Apr 2, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-expression
finite-automata
+
–
1
votes
0
answers
237
Peter Linz Edition 4 Exercise 3.1 Question 24,25 (Page No. 77)
Formal languages can be used to describe a variety of two-dimensional figures. Chain-code languages are defined on the alphabet $Σ =$ {$u, d, r, l$ }, where these symbols stand for unit-length straight lines in ... is a closed contour in the sense that the beginning and ending points are the same? Are these conditions also necessary?
Formal languages can be used to describe a variety of two-dimensional figures. Chain-codelanguages are defined on the alphabet $Σ =$ {$u, d, r, l$ }, where these symbols...
Naveen Kumar 3
506
views
Naveen Kumar 3
asked
Apr 2, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-expression
+
–
0
votes
0
answers
238
Peter Linz Edition 4 Exercise 3.1 Question 23 (Page No. 77)
For the case of a regular expression $r$ that does not involve $λ$ or $Ø$, give a set of necessary and sufficient conditions that $r$ must satisfy if $L(r)$ is to be infinite.
For the case of a regular expression $r$ that does not involve $λ$ or $Ø$, give a set of necessary and sufficient conditions that $r$ must satisfy if $L(r)$ is to be in...
Naveen Kumar 3
296
views
Naveen Kumar 3
asked
Apr 2, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-expression
+
–
0
votes
0
answers
239
Peter Linz Edition 4 Exercise 3.1 Question 22 (Page No. 77)
Prove rigorously that the expressions in $r= (1^*011^*)^* (0 + λ) + 1^* (0 + λ)$ do indeed denote the specified language.
Prove rigorously that the expressions in $r= (1^*011^*)^* (0 + λ) + 1^* (0 + λ)$ do indeed denote the specified language.
Naveen Kumar 3
193
views
Naveen Kumar 3
asked
Apr 2, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-expression
+
–
0
votes
1
answer
240
Peter Linz Edition 4 Exercise 3.1 Question 21 (Page No. 77)
Give a general method by which any regular expression $r$ can be changed into $\widehat{r}$ such that $(L(r))^R = L(\widehat{r})$.
Give a general method by which any regular expression $r$ can be changed into $\widehat{r}$ such that $(L(r))^R = L(\widehat{r})$.
Naveen Kumar 3
623
views
Naveen Kumar 3
asked
Apr 2, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-expression
+
–
Page:
« prev
1
...
3
4
5
6
7
8
9
10
11
12
13
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register