The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged regulargrammar
0
votes
0
answers
1
Peter Linz Edition 4 Exercise 5.2 Question 11 (Page No. 145)
Is it possible for a regular grammar to be ambiguous?
asked
Apr 14
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
7.1k
points)

12
views
peterlinz
theoryofcomputation
regulargrammar
ambiguous
0
votes
0
answers
2
Peter Linz Edition 4 Exercise 3.3 Question 17 (Page No. 97)
Let $G_1 = (V_1,Σ,S_1,P_1)$ be rightlinear and $G_2= (V_2, Σ,S_2,P_2)$ be a leftlinear grammar, and assume that $V_1$ and $V_2$ are disjoint. Consider the linear grammar $G =(${$S$}$ ∪ V_1 ∪ V_2, Σ,S, P)$, where $S$ is not in $V_1 ∪ V_2$ and $P =$ {$S → S_1S_2$}$ ∪ P_1 ∪ P_2$. Show that $L(G)$ is regular.
asked
Apr 3
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
7.1k
points)

9
views
peterlinz
theoryofcomputation
regulargrammar
0
votes
2
answers
3
Peter Linz Edition 4 Exercise 3.3 Question 15 (Page No. 97)
Show that any regular grammar $G$ for which $L (G) ≠ Ø$ must have at least one production of the form $A → x$ where $A ∈ V$ and $x ∈ T^ *$.
asked
Apr 3
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
7.1k
points)

25
views
peterlinz
theoryofcomputation
regulargrammar
0
votes
0
answers
4
Peter Linz Edition 4 Exercise 3.3 Question 14 (Page No. 97)
Show that for every regular language not containing $λ$ there exists a rightlinear grammar whose productions are restricted to the forms $A → aB$, or $A → a$, where $A, B ∈ V,$ and $a ∈ T$
asked
Apr 3
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
7.1k
points)

5
views
peterlinz
theoryofcomputation
regulargrammar
0
votes
0
answers
5
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}.
asked
Apr 3
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
7.1k
points)

8
views
peterlinz
theoryofcomputation
regulargrammar
0
votes
0
answers
6
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 } .
asked
Apr 3
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
7.1k
points)

4
views
peterlinz
theoryofcomputation
regulargrammar
0
votes
0
answers
7
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}.
asked
Apr 3
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
7.1k
points)

3
views
peterlinz
theoryofcomputation
regulargrammar
0
votes
0
answers
8
Peter Linz Edition 4 Exercise 3.3 Question 10 (Page No. 97)
Find a leftlinear grammar for the language $L ((aab^*ab)^*).$
asked
Apr 3
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
7.1k
points)

14
views
peterlinz
theoryofcomputation
regulargrammar
0
votes
0
answers
9
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.
asked
Apr 3
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
7.1k
points)

6
views
peterlinz
theoryofcomputation
regulargrammar
0
votes
0
answers
10
Peter Linz Edition 4 Exercise 3.3 Question 6 (Page No. 97)
Construct a rightlinear grammar for the language $L ((aab^*ab)^*)$.
asked
Apr 3
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
7.1k
points)

4
views
peterlinz
theoryofcomputation
regulargrammar
0
votes
0
answers
11
Peter Linz Edition 4 Exercise 3.3 Question 5 (Page No. 96)
Find a leftlinear grammar for the language accepted by the nfa below.
asked
Apr 3
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
7.1k
points)

2
views
peterlinz
theoryofcomputation
regulargrammar
0
votes
0
answers
12
Peter Linz Edition 4 Exercise 3.3 Question 4 (Page No. 96)
Construct right and leftlinear grammars for the language $L =$ {$a^nb^m : n ≥ 2, m ≥ 3$}.
asked
Apr 3
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
7.1k
points)

3
views
peterlinz
theoryofcomputation
regulargrammar
0
votes
0
answers
13
Peter Linz Edition 4 Exercise 3.3 Question 3 (Page No. 96)
Construct a leftlinear grammar for the language generated by the grammar $S → abA,$ $A → baB,$ $B → aAbb.$
asked
Apr 3
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
7.1k
points)

2
views
peterlinz
theoryofcomputation
regulargrammar
0
votes
0
answers
14
Peter Linz Edition 4 Exercise 3.3 Question 2 (Page No. 96)
Find a regular grammar that generates the language $L (aa^* (ab+ a)^*)$ .
asked
Apr 3
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
7.1k
points)

3
views
peterlinz
theoryofcomputation
regulargrammar
0
votes
0
answers
15
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 → aAbb$ .
asked
Apr 3
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
7.1k
points)

4
views
peterlinz
theoryofcomputation
regulargrammar
0
votes
1
answer
16
Peter Linz Edition 4 Exercise 3.1 Question 5 (Page No. 75)
what is the regular grammar for L={$a^nb^m$  n+m is even}
asked
Feb 24
in
Theory of Computation
by
aditi19
Active
(
2.9k
points)

165
views
theoryofcomputation
peterlinz
finiteautomata
regularlanguages
regularexpressions
regulargrammar
+1
vote
0
answers
17
Peter Linz Edition 4 Exercise 3.3 Question 6 (Page No. 97)
Construct a right linear grammar for the language $L((aab^*ab)^*)$ is this grammar correct? S>aaA  ε A>bA  abA  S
asked
Feb 24
in
Theory of Computation
by
aditi19
Active
(
2.9k
points)

46
views
theoryofcomputation
peterlinz
finiteautomata
regularlanguages
regulargrammar
0
votes
1
answer
18
Practice Question
How to prove that $ (a+b)^*ab(a+b)^*+b^*a^* = (a+b)^*$
asked
Jan 14
in
Theory of Computation
by
Hardik Maheshwari
(
123
points)

54
views
theoryofcomputation
regularexpressions
regularlanguages
regulargrammar
0
votes
1
answer
19
UGC NET Doubt
https://gateoverflow.in/13365/ugcnetdec2014iii24 i’ve a small doubt in the solution of this question how is (a+b)*ba(a+b)* complement of the given language?
asked
Dec 14, 2018
in
Theory of Computation
by
aditi19
Active
(
2.9k
points)

65
views
ugc
regularlanguages
regulargrammar
0
votes
0
answers
20
Self doubt about relation between regular and linear grammar
If a grammar G is both left linear as well as right linear then,what should be the case a) G is always not regular b) G may or may not be regular c) something else
asked
Nov 30, 2018
in
Theory of Computation
by
Abbas Ahmad
(
135
points)

32
views
theoryofcomputation
regulargrammar
finiteautomata
0
votes
1
answer
21
GATEBOOK2019TOC113
Which of the following grammar is a regular grammar and generates the same language as the regular expression $a^*+b^*+ ab?$ $S\to AB,\:A\to aA \mid \epsilon;\:B\to bB\mid \epsilon$ $S\to ab \mid A \mid B; \: A\to Aa \mid a;\: B\to Bb \mid b$ $S\to ab \mid A \mid B; \: A\to aA \mid \epsilon;\: B\to bB \mid \epsilon$ $S\to A\mid B;\: A\to aA \mid b;\: B\to Bb \mid b$
asked
Nov 12, 2018
in
Theory of Computation
by
GATEBOOK
Boss
(
17.2k
points)

61
views
gb2019toc1
regulargrammar
0
votes
1
answer
22
Are these two languages equal?
L1=ab* L2=a(aa)*b(bb)* Are the languages equal if not what relation do they satisfy?
asked
Nov 6, 2018
in
Theory of Computation
by
sripo
Active
(
2.6k
points)

40
views
theoryofcomputation
regularlanguages
regulargrammar
0
votes
0
answers
23
This question is taken from a sample paper
Consider the following grammar G. Is this regular? S →EF E → a∈ F → abFac
asked
Nov 3, 2018
in
Theory of Computation
by
Piyush Agarwal 1
(
23
points)

16
views
finiteautomata
regularlanguages
regulargrammar
0
votes
1
answer
24
I came across this in a test paper
Consider the following grammar G. Is this regular? S →EF E → a∈ F → abFac
asked
Nov 3, 2018
in
Theory of Computation
by
Piyush Agarwal 1
(
23
points)

16
views
regulargrammar
regularlanguages
finiteautomata
+1
vote
1
answer
25
Grammar to DFA Construction
For the given Grammar S>aAbB A>bCaS B>aCbS C>aBbA Construct DFA I am getting confused in understanding how to take the final state.
asked
Oct 13, 2018
in
Theory of Computation
by
sripo
Active
(
2.6k
points)

66
views
theoryofcomputation
finiteautomata
regulargrammar
numberofdfa
minimalstateautomata
0
votes
0
answers
26
regular grammar
If a is a terminal and S, A, B are three nonterminals, then which of the following are regular grammars? (a) S → ε, A → aSb (b) A → aBa, B → bAb (c) A → BaBab (d) A → abBaB answer given is b. but I think all are regular grammars. please clear my doubt.
asked
Sep 29, 2018
in
Theory of Computation
by
Ananya Jaiswal 1
Active
(
2.2k
points)

36
views
theoryofcomputation
regulargrammar
0
votes
1
answer
27
conversion of right linear grammar to DFA
In converting right linear regular grammar to DFA how to determine the final states? Can anyone tell the procedure?
asked
Sep 16, 2018
in
Theory of Computation
by
sushmita
Boss
(
17k
points)

72
views
theoryofcomputation
finiteautomata
regulargrammar
nfa
0
votes
1
answer
28
Regular Grammar
Is there any difference between Type 3 grammar and regular grammar?
asked
Jul 5, 2018
in
Theory of Computation
by
Gaurav Parashar
(
187
points)

58
views
regulargrammar
theoryofcomputation
compilerdesign
0
votes
1
answer
29
self doubt
What is the differene between { Φ } and λ and what happens when we concatenate this with a regular language ??
asked
Apr 25, 2018
in
Theory of Computation
by
ankit aingh
(
219
points)

51
views
theoryofcomputation
regulargrammar
Page:
1
2
next »
Quick search syntax
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
IIT BHUBANESWAR MTECH WRITTEN TEST/INTERVIEW
GATE score validity queries.
How to prepare for IISC Interdisciplinary Mathematical Sciences Interview
GO Hardcopy for GATE 2020
How to prepare for BARC interview
Follow @csegate
Recent questions tagged regulargrammar
Recent Blog Comments
10000 to <2000 is really kind of achievement , my...
THey removed it this year... I did not check it,...
even though i am not going for iiit , can you...
I don't think IIITD requires any codechef...
Will apply for IIITB. IIIT D requires a codechef...
50,108
questions
53,221
answers
184,627
comments
70,462
users