# Recent questions tagged regular-grammar

1
Which of the following are undecidable? $P1$: The language generated by some CFG contains any words of length less than some given number $n$. $P2$: Let $L1$ be CFL and $L2$ be regular, to determine whether $L1$ and $L2$ have common elements $P3$: Any given CFG is ambiguous or not. ... CFG $G$, to determine whether epsilon belongs to $L(G)$ $P2$ only $P1$ and $P2$ only $P2$ and $P3$ only $P3$ only
2
A->aB/bA/b B->aC/bB C->aA/bC/a If the above regular grammar is converted into DFA then how many final states will be there? According to me there should be 2 final states: A and C But the resource from where I am reading it says only one final state will be there which will be A. Kindly explain.
3
Is it possible for a regular grammar to be ambiguous?
4
Let $G_1 = (V_1,Σ,S_1,P_1)$ be right-linear and $G_2= (V_2, Σ,S_2,P_2)$ be a left-linear 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_1|S_2$}$∪ P_1 ∪ P_2$. Show that $L(G)$ is regular.
5
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^ *$.
6
Show that for every regular language not containing $λ$ there exists a right-linear grammar whose productions are restricted to the forms $A → aB$, or $A → a$, where $A, B ∈ V,$ and $a ∈ T$
7
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}.
8
Find a regular grammar that generates the language $L=$ {$w∈$ {$a,b$}$^*:n_a(w)+3n_b(w)$ is even } .
9
Find a regular grammar for the language $L =$ {$a^nb^m : n + m$ is even}.
10
Find a left-linear grammar for the language $L ((aab^*ab)^*).$
11
Find a regular grammar that generates the language on $Σ =$ {$a, b$} consisting of all strings with no more than three $a$'s.
12
Find a left-linear grammar for the language accepted by the nfa below.
13
Construct right- and left-linear grammars for the language $L =$ {$a^nb^m : n ≥ 2, m ≥ 3$}.
14
Construct a left-linear grammar for the language generated by the grammar $S → abA,$ $A → baB,$ $B → aA|bb.$
15
Find a regular grammar that generates the language $L (aa^* (ab+ a)^*)$ .
16
Construct a dfa that accepts the language generated by the grammar $S → abA, A → baB, B → aA|bb$ .
1 vote
17
what is the regular grammar for L={$a^nb^m$ | n+m is even}
1 vote
18
Construct a right linear grammar for the language $L((aab^*ab)^*)$ is this grammar correct? S->aaA | ε A->bA | abA | S
19
How to prove that $(a+b)^*ab(a+b)^*+b^*a^* = (a+b)^*$
20
https://gateoverflow.in/13365/ugcnet-dec2014-iii-24 i’ve a small doubt in the solution of this question how is (a+b)*ba(a+b)* complement of the given language?
21
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
22
L1=ab* L2=a(aa)*b(bb)* Are the languages equal if not what relation do they satisfy?
23
Consider the following grammar G. Is this regular? S →EF E → a|∈ F → abF|ac
24
Consider the following grammar G. Is this regular? S →EF E → a|∈ F → abF|ac
1 vote
25
For the given Grammar S->aA|bB A->bC|aS B->aC|bS C->aB|bA Construct DFA I am getting confused in understanding how to take the final state.
26
If a is a terminal and S, A, B are three non-terminals, then which of the following are regular grammars? (a) S → ε, A → aS|b (b) A → aB|a, B → bA|b (c) A → Ba|Bab (d) A → abB|aB answer given is b. but I think all are regular grammars. please clear my doubt.
1 vote
27
In converting right linear regular grammar to DFA how to determine the final states? Can anyone tell the procedure?
$S\rightarrow AB$ $A\rightarrow a$ $B\rightarrow b$ The language generated by the above grammar is ab and since we can give a FA for the language then it must be a regular language.Now,since the given grammar generates a regular language then it must be a regular grammar but again it is not in the form of TYPE 3 or regular grammar,then how to identify if the grammar is regular or not?