Register

Recent questions tagged context-free-language

3 3 votes
2 2 answers
3.7k
3.7k views
UGC NET CSE | June 2012 | Part 3 | Question: 39
The following CFG $S \rightarrow aB \mid bA, A \rightarrow a \mid as \mid bAA, B \rightarrow b \mid bs \mid aBB$ generates strings of terminals that haveodd number of a’s...
User Avatar
3 3 votes
2 answers 2 answers
6.5k
6.5k views
UGC NET CSE | June 2012 | Part 3 | Question: 32
The equivalent grammar corresponding to the grammar $G:S \rightarrow aA, A \rightarrow BB, B \rightarrow aBb \mid \varepsilon$ is$S \rightarrow aA, A \rightarrow BB, B \r...
User Avatar
2 2 votes
0 0 answers
1.2k
1.2k views
Among these language which is/are Context free Language and has Context Free Grammar ?
Among these languages which is/are Context free Language and has Context Free Grammar ? please Explain the reason a little bit .1 .LISP2 .C-Language3 .C++ Language4 .Cobo...
User Avatar
1 1 vote
2 answers 2 answers
1.9k
1.9k views
network 200.20.11.144/27 , Which of the following languages are context free
In the network 200.20.11.144/27, the fourth octet (in decimal) of the last IP address of the network which can be assigned to a host is____Which of the following language...
User Avatar
8 8 votes
4 answers 4 answers
6.1k
6.1k views
ISRO CSE 2011 | Question: 68
Which of the following sentences can be generated by S - aS $\mid$ bAA - d $\mid$ cAbccddabbccaabcabcabcd
User Avatar
3 3 votes
1 answers 1 answer
884
884 views
TOC CFG
If language $L=\{a^n b^n \mid n \geq 0\}$, then language $L^2$ is given by$\{a^{2n} b^{2n} \mid n \geq 0\}$$\{a^n b^n a^n b^n \mid n \geq 0\}$$\{a^n b^n \mid n \geq 0\}$$...
User Avatar
1 1 vote
2 answers 2 answers
820
820 views
Toc CFG
The production rules for a given context-free grammar are $S \rightarrow aA, A \rightarrow bB, A \rightarrow aB$ and $B \rightarrow a$ inChomsky normal formGreibach norma...
User Avatar
0 0 votes
1 answers 1 answer
3.5k
3.5k views
TOC , Language ,PDA
What does this Language Represents ? And what is the machine which is able to represent this Language.L = { a^i b^j c^k d^l } where i = k or j = lHow it is different fro...
User Avatar
10 10 votes
8 8 answers
14.6k
14.6k views
ISRO CSE 2008 | Question: 7
Consider the grammar$S \rightarrow ABCc \mid bc$$BA \rightarrow AB$$Bb \rightarrow bb$$Ab \rightarrow ab$$Aa \rightarrow aa$Which of the following sentences can be derive...
User Avatar
2 2 votes
1 answers 1 answer
2.2k
2.2k views
UGC NET CSE | June 2014 | Part 2 | Question: 09
The context free grammar for the language $L= \left\{a^{n}b^{m}c^{k} \mid k = \mid n - m\mid , n \geq 0, m \geq 0, k \geq 0\right\}$ is $S \rightarrow S_{1}S_{3}, S_{1} \...
User Avatar
1 1 vote
2 answers 2 answers
1.4k
1.4k views
Automata Language PDA
If a given CFL Language is L= {a^n b^n ;n>=0} then how can we determine the value of L^2 .Explain with an example .
User Avatar
2 2 votes
3 answers 3 answers
4.4k
4.4k views
UGC NET CSE | December 2015 | Part 3 | Question: 28
Given the following two languages:$L_1=\{a^nba^n\;|\;n>0\}$$L_2=\{a^nba^nb^{n+1}\;|\;n>0\}$Which of the following is correct? $L_1$ is context free language and $L_2$ is ...
User Avatar
3 3 votes
1 answers 1 answer
4.9k
4.9k views
Is this language be accepted by 2 stack PDA L={a^n b^m c^n d^m / n>=m}
User Avatar
12 12 votes
1 answers 1 answer
2.6k
2.6k views
ISI2015-PCB-CS-5b
Construct a context free grammar (CFG) to generate the following language:$L = \{a^nb^mc^{n+m}: \text{n, m are integers, and } n \geq 1, m \geq 1 \}$
User Avatar
3 3 votes
1 answers 1 answer
4.5k
4.5k views
Which of these languages are NOT context free?
Let$l1 =\{ 0^{n+m} 1^n 0^m \mid n,m>= 0 \}$,$l2 = \{ 0^{n+m} 1^{n+m} 0^m \mid n,m>=0 \}$ ,$l3 = \{ 0^{n+m} 1^{n+m} 0^{n+m} \mid n,m>=0 \}$Which of these languages are NOT...
User Avatar
85 85 votes
9 answers 9 answers
37.9k
37.9k views
GATE CSE 2016 | Set 1 | Question: 42
Consider the following context-free grammars;$G_1 : S \to aS \mid B, B \to b \mid bB$$G_2 : S \to aA \mid bB, A \to aA \mid B \mid \varepsilon,B \to bB \mid \varepsilon$W...
User Avatar
68 68 votes
9 answers 9 answers
19.6k
19.6k views
GATE CSE 2016 | Set 1 | Question: 16
Which of the following languages is generated by the given grammar?$$S \rightarrow aS \mid bS \mid \varepsilon$$$\{ a^nb^m \mid n,m \geq 0\}$$\{ w \in \{ a,b\}^* \mid w\t...
User Avatar
70 70 votes
7 answers 7 answers
36.1k
36.1k views
GATE CSE 2016 | Set 2 | Question: 43
Consider the following languages:$L_{1}=\left\{a^{n}b^{m}c^{n+m}:m, n\geq 1\right\}$$L_{2}=\left\{a^{n}b^{n}c^{2n} :n\geq 1\right\}$Which one of the following is TRUE?Bot...
User Avatar
66 66 votes
4 answers 4 answers
21.1k
21.1k views
GATE CSE 2016 | Set 2 | Question: 18
Consider the following types of languages: $L_{1}$: Regular, $L_{2}$: Context-free, $L_{3}$: Recursive, $L_{4}$: Recursively enumerable. Which of the following is/are TRU...
User Avatar
5 5 votes
4 answers 4 answers
10.8k
10.8k views
If L1 is Regular, and L1UL2 is regular, then L2 is?
Consider L1, L2 ⊆ Ʃ* such that L1 and L1 ∪ L2 are regular.(a) L2 is definitely regular(b) L2 may not be regular(c) L2 is context free(d) None of aboveIs it option B or C?...
User Avatar
0 0 votes
0 0 answers
500
500 views
CFG regular or NOT
How to identify regular CFG
User Avatar
1 1 vote
1 answers 1 answer
607
607 views
Answer given as (C). Can't understand why ??
User Avatar
1 1 vote
1 answers 1 answer
597
597 views
Which of the following is true ??
Q.: 13\[\begin{array}{l}\mathrm{L}_{1}=\left\{(\mathrm{xy})^{\mathrm{m}}(\mathrm{yz})^{\mathrm{m}}, \mathrm{~m} \geq 1\right\} \\\mathrm{L}_{2}=\left\{\mathrm{a}^{m} \mat...
User Avatar
2 2 votes
1 answers 1 answer
820
820 views
CFL production
Are grammars with $S \to SS$ productions always ambiguous?Also, how can the production be represented in form of a formula? For example, $S \to aSb \mid \varepsilon$ can ...
User Avatar
3 3 votes
1 1 answer
6.1k
6.1k views
Complement of a recursive language
Given a TM M, complement of L(M) is context-free. True/False?
User Avatar
1 1 vote
1 answers 1 answer
841
841 views
Regular - CFG
Consider the language L1 = { apbqcr / p,q,r >= 0} and L2 = { apbqcr ​/ p,q,r >= 0 and p=r} Then L1 - L2 is regular of CFL ?
User Avatar
5 5 votes
2 answers 2 answers
6.3k
6.3k views
Complement of CSL
Please some one explain. why complement of this language is CFL.
User Avatar
2 2 votes
2 2 answers
913
913 views
Is $ a terminal or not ?
Follow(S) comes as {(, ). $ }So, do we count $ as terminal or not.Could anyone please tell me, $ should be considered as terminal or not ? Although I think, I should not...
User Avatar
3 3 votes
2 answers 2 answers
2.4k
2.4k views
CFL or CSL ?
Is the language given by $ww^R ww^R$, where $w$ is any string over the binary alphabet, Context Free or Context Sensitive?
User Avatar
5 5 votes
4 answers 4 answers
3.6k
3.6k views
PDA
Consider the following push down automata.The language accepted by above PDA is_______.Regular but infinite.DCFL but not regular.CFL but not DCFLFinite language.
User Avatar
Page: