search
Log In

Recent questions tagged cfg

0 votes
0 answers
1
Show that the problem of determining whether a CFG generates all strings in $1^{\ast}$ is decidable. In other words, show that $\{\langle { G \rangle} \mid \text{G is a CFG over {0,1} and } 1^{\ast} \subseteq L(G) \}$ is a decidable language.
asked Oct 17, 2019 in Theory of Computation Lakshman Patel RJIT 69 views
0 votes
0 answers
2
Let $\Sigma = \{0,1\}$. Show that the problem of determining whether a $CFG$ generates some string in $1^{\ast}$ is decidable. In other words, show that $\{\langle {G \rangle}\mid \text{G is a CFG over {0,1} and } 1^{\ast} \cap L(G) \neq \phi \}$ is a decidable language.
asked Oct 17, 2019 in Theory of Computation Lakshman Patel RJIT 28 views
0 votes
1 answer
4
$L1 =\left \{ a^{m} b^{n} c^{p} | \left ( m \geq n \right )\text{or} \left ( n = p \right ) \right \}$ $L2 =\left \{ a^{m} b^{n} c^{p} | \left ( m \geq n \right )\text{and} \left ( n = p \right ) \right \}$ $(a)$ Both are NCFL’s $(b)$ L1 is DCFL and L2 is NCFL $(c)$ L1 is NCFL and L2 is not context-free $(d)$ Both are not context-free
asked May 23, 2019 in Theory of Computation Hirak 177 views
0 votes
0 answers
6
consider following grammer S → aSb / aSbb / aSbbb / ….. is language generated by above grammer is DCFL?
asked Dec 24, 2018 in Theory of Computation Rahul_Rathod_ 114 views
0 votes
0 answers
7
Consider a push down automata (PDA) below which runs over the input alphabet (a, b). It has the stack alphabet {z0, X}, where z0 is the bottom of stack marker. The set of states of PDA is {q0,q1} where q0 is the start state and rules of the PDA are, (The languare accepted by the grammar is)
asked Nov 30, 2018 in Theory of Computation rahuljai 184 views
0 votes
0 answers
8
Consider the following CFG 'G' S--> aA/bSS/SS A--> aAb/bAa/AA/ε The language generated by G is: a)Set of all strings with atleast one 'a' b)Set of all strings with atleast two a's c)Set of all strings with atleast one more 'a' than number of b's d)None of these
asked Oct 18, 2018 in Theory of Computation Sambhrant Maurya 106 views
0 votes
0 answers
9
L1 = { a^n b^n c^m | n,m>=0} L2 = { a^m b^n c^n | m,n>=0} L1 intersection L2 = { { a^n b^n c^n | n>=0} how we do intersection plz explain using grammer....
asked Oct 1, 2018 in Theory of Computation bhavnakumrawat5 40 views
–2 votes
0 answers
10
L={an . bn . cm . cn | m,n ≥ 0 } find CFG of corresponding Language
asked Sep 19, 2018 in Theory of Computation amit166 47 views
1 vote
2 answers
11
Consider the following CFG. S → aSa | bSb | a | b | ε For the above CFG, the total number of strings generated whose length is less than or equal to 8 [exclude the empty string] is _____________.
asked Jul 31, 2018 in Theory of Computation himgta 147 views
0 votes
1 answer
12
L = {x^a y^a : a ≥ 1} I. L^3 is context free. II. ⌈√ L⌉ is not context free. Which of the following is correct? (a) I only (b) II only (c) Both I and II (d) None of the above
asked Jul 30, 2018 in Theory of Computation himgta 52 views
1 vote
1 answer
13
Whether a given context-free language is regular is decidable or undecidable? Prove your answer!
asked Jul 29, 2018 in Theory of Computation himgta 97 views
3 votes
1 answer
14
Let $L=\{w \mid w \in (0+1)^+ , N_0(w) \le N_1(w) \le 2N_0(w) \}$,where $N_i(w)$ represents number of $i's$ in string $w$. a) Give a CFG for $L$ b) is Lc = Σ*- L context - free? c) Let $\frac{1}{2}$L = $\{x | ∃y ∈ L , |x| = |y| , x.y ∈ L \}$.is $\frac{1}{2}$L context-free?
asked Apr 30, 2018 in Theory of Computation Sambit Kumar 306 views
1 vote
2 answers
15
Consider Grammar G with the following characteristic- $A → ax$, where $A ∈ V$, $a ∈ T$, $x ∈ V^*$, and any pair $( A, a )$ occurs at most once in $P$. For example, $S → aA \mid aB...,$ is not a grammar of type $G$ because the pair $(S,a)$ occur in two productions. Which of ... a string w belonging to $L(G)$ ? $\mid w \mid^3$ $\mid w \mid$ $2^{\mid w \mid}$ Not a function of $\mid w \mid$ alone.
asked Feb 24, 2018 in Theory of Computation tarun_svbk 441 views
1 vote
0 answers
16
Is equivalence problem decidable in case of-: 1) CFG's 2) DCFG's If yes, then how?
asked Jan 19, 2018 in Theory of Computation Aakanchha 60 views
2 votes
0 answers
17
I'm studying through Linz and Have few confusions : Let $\sum = {a, b} then \sum ^{\bigstar} = \epsilon ,a,b,aa,ab,ba,bb,aaa,aab,..... Here can we take ba ? I mean placing doesn't matter ?$ ... w) = nb (w) and na (v) = nb (v) , where v is any prefix of w } . I'm not getting this whole notation ,please explain thank you !
asked Jan 16, 2018 in Theory of Computation _shashi 72 views
0 votes
0 answers
18
0 votes
1 answer
19
If the start symbol derives epsilon.Can we eliminate all epsilons while converting to Chomsky Normal Form?Following question from ullman the answer given they have removed the epsilon.But I think if the start symbol derives epsilon,more accurately if L(G) contains epsilon we cannot remove it. S->ASB|epsilon A->aAS|a B->SbS|A|bb
asked Nov 25, 2017 in Theory of Computation Surajit 259 views
4 votes
3 answers
20
Determine the minimum height of parse tree in CNF for terminal string of length w, which is constructed by using CFG G (a) log2|w|+1 (b) log2|w| (c) log2|w|−1 (d) None of these
asked Nov 19, 2017 in Theory of Computation Pranav Madhani 1.5k views
1 vote
2 answers
21
Consider the language defined by the regular expression (a | b) * b+. Which of the following regular expressions also define that language? (i) (a*b+) | (b*b+) (ii) (ab |bb)*b* (iii) (a | b | ba)*b+ (a) i only (b) i & ii only (c) iii only (d) All of these Solution: Option (c) Need explanation why not all? we can obtain only b by taking (a | b) null it also applies to a option then why not a?
asked Nov 19, 2017 in Theory of Computation Pranav Madhani 422 views
0 votes
1 answer
22
Consider this grammar: S → SS | a How many derivation trees are possible for a4? (a) 3 (b) 4 (c) 5 (d) 6 how to generalize for any values if a^5 or a^7 is there any general formulae?
asked Nov 18, 2017 in Theory of Computation Pranav Madhani 304 views
0 votes
1 answer
23
Consider 2 regular expression: i. ϕ* + a+ + b+ + (a + b)+ → r1 ii. ϕ+ + a* + b* + (a + b)* → r2 (a) L(r1) = L(r2) (b) L(r1) ⊆ L(r2) (c) L(r1) ⊇ L(r2) (d) None of above Solution: Option (a) how need explanation? wont answer be c?
asked Nov 17, 2017 in Theory of Computation Pranav Madhani 318 views
0 votes
1 answer
24
This is the Gate Question - https://gateoverflow.in/3392/gate2008-it-78?show=155376#c155376 I couln't help but understand the balanced paranthesis thing, I know, () this is balanced, (( )) is balanced, ((( ))) is balanced, but how's that working in that gate ... Also, I didn't have any intention to make a duplicate question/thread, I will close this question whenever I get my doubt solved. Thanks!
asked Sep 26, 2017 in Theory of Computation iarnav 118 views
1 vote
1 answer
25
L = {a^nb^m : n >= m+3} below context grammer is correct?? S ==> aA | Aa A ==> aAb | bAa | abA | baA | aa
asked Jul 12, 2017 in Theory of Computation akhileshreddy 128 views
2 votes
1 answer
26
0 votes
1 answer
27
How to solve this? Design CFG for the language {aibjck | i=j+k}
asked Apr 13, 2017 in Theory of Computation csuprriya 80 views
0 votes
1 answer
28
Do the following productions mean the same Bb->bb and B->b My doubt is that will the first production be used only when we have b in the follow of B or it can be used in any case. If it can be used in any case then will the first production be equal to second production.
asked Apr 4, 2017 in Theory of Computation Srinivas Rao 259 views
1 vote
1 answer
29
Construct context-free grammars to accept the following languages. $\begin{align*} \large L = \left \{ 0^i1^j2^k \;\; | \;\; i \neq j \;\; or \;\; j \neq k \right \} \end{align*}$
asked Mar 25, 2017 in Theory of Computation gabbar 301 views
0 votes
0 answers
30
L1 = {an bm | n ≤ m ≤ 2n} L2 = {an bm│m≠n & m≠2n} Which of the following is true? A. Only L1 is CFG B. Only L2 is CFG C. Both are CFG D. None of them is CFG
asked Jan 26, 2017 in Theory of Computation AmitPatil 166 views
...