Recent questions tagged cfg

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.
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.
3
Let $A\varepsilon_{CFG} = \{ \langle{ G }\rangle \mid G\: \text{is a CFG that generates}\: \epsilon \}.$Show that $A\varepsilon_{CFG}$ is decidable.
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
1 vote
5
6
consider following grammer S → aSb / aSbb / aSbbb / ….. is language generated by above grammer is DCFL?
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)
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
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....
10
L={an . bn . cm . cn | m,n ≥ 0 } find CFG of corresponding Language
1 vote
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 _____________.
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
1 vote
13
Whether a given context-free language is regular is decidable or undecidable? Prove your 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?
1 vote
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.
1 vote
16
Is equivalence problem decidable in case of-: 1) CFG's 2) DCFG's If yes, then how?
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 !
18
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
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
1 vote
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?
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?
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?
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!
1 vote
25
L = {a^nb^m : n >= m+3} below context grammer is correct?? S ==> aA | Aa A ==> aAb | bAa | abA | baA | aa
26
S->ASB A->aASA | a | ϵ B->SbS | A | bb Convert this grammar into Chomsky Normal Form
27
How to solve this? Design CFG for the language {aibjck | i=j+k}
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*}