search
Log In

Recent questions tagged regular-grammar

0 votes
2 answers
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
asked Mar 30 in Theory of Computation Lakshman Patel RJIT 177 views
2 votes
2 answers
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.
asked Jun 3, 2019 in Theory of Computation Akash Kumar Roy 510 views
0 votes
0 answers
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.
asked Apr 3, 2019 in Theory of Computation Naveen Kumar 3 30 views
0 votes
2 answers
5
0 votes
0 answers
6
0 votes
0 answers
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}.
asked Apr 3, 2019 in Theory of Computation Naveen Kumar 3 22 views
0 votes
1 answer
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?
asked Dec 14, 2018 in Theory of Computation aditi19 293 views
0 votes
0 answers
21
0 votes
1 answer
22
0 votes
1 answer
23
0 votes
1 answer
24
1 vote
1 answer
25
0 votes
0 answers
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.
asked Sep 29, 2018 in Theory of Computation Ananya Jaiswal 1 77 views
1 vote
2 answers
27
0 votes
1 answer
28
0 votes
1 answer
29
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 ankit aingh 72 views
1 vote
3 answers
30
$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?
asked Apr 6, 2018 in Theory of Computation Sourav_35 438 views
...