Register

Recent questions tagged context-free-language

390
views
1 answers
0 votes
Dcfl union Regular not always dcfl?
$L=\{a^mb^n\mid m≠n\}∪{(a+b)^∗b(b+a)^*a(a+b)^∗}$$\implies L = \;\{a^mb^n\mid m<n\} \cup \{a^mb^n\mid m>n\} \cup (a+b)^*b(a+b)^*a(a+b)^*$ It is DCFL ∪ Regular, ...
User Avatar
1.4k
views
1 answers
1 votes
identify language is regular or not L={wcw^r | w,c belongs to E*} E={a,b}
identify language is regular or not L={wcw^r | w,c belongs to E*} E={a,b}if yes then why please explain
User Avatar
339
views
0 answers
1 votes
Self Doubt about Construction of CFG
I am trying to construct a CFG for this following langauge: L = $\{0^i 1^j | i \neq j \ and \ i, j 0\}$, this is what I came up with:$ S \rightarrow A \ | \ B $$A \righ...
User Avatar
7.5k
views
2 answers
24 votes
GATE CSE 2022 | Question: 37
Consider the following languages:$L_{1} = \{ a^{n} wa^{n} | w \in \{a,b\}^{\ast}\}$$L_{2} = \{wxw^{R} | w, x \in \{a,b\}^{*}, |w|, |x| 0 \}$Note that $w^{R}$ is the reve...
User Avatar
11.9k
views
3 answers
20 votes
GATE CSE 2022 | Question: 38
Consider the following languages:$L_{1} = \{ ww | w \in \{a,b\}^{\ast} \}$$L_{2} = \{a^{n} b^{n} c^{m} | m,n \geq 0 \}$$L_{3} = \{a^{m} b^{n} c^{n} | m,n \geq 0 \}$Which ...
User Avatar
803
views
2 answers
1 votes
DCFL - TOC
Is the following language a DCFL? Please explain your reasoning.
User Avatar
951
views
1 answers
0 votes
parse tree - context-free grammars - TOC
Given a CFG and a string, what is the relation between the number of leftmost derivations, the number of rightmost derivations and the number of parse trees?
User Avatar
964
views
2 answers
0 votes
made easy test series - parsing - context-free grammar
Consider the following context-free grammar:Find the number of unique productions in {Goto (A → D.BC, B) U Goto (A → .DBC, D)}
User Avatar
638
views
2 answers
3 votes
#Gate CS Applied Course Mock Test
Is this Language a CFL?If yes, Can you please explain the implementation.
User Avatar
1.3k
views
3 answers
2 votes
regular and cfl
if L1 and L2 are not regular language then L1 union L2 is not regular.this statement is true or false?my approach is:::true let suppose L1= a^n b^n AND L2= a^k b^kbot...
User Avatar
972
views
3 answers
3 votes
#selfDoubt
complement of CFL can never be CFL.please explain if the above statement is true of false?
User Avatar
488
views
1 answers
0 votes
Closure Properties of Languages
let L = “CFL but not REGULAR”, Can we get complement of L as CFL?Unlike in the case of Recursively Enumerable(RE) language where if L = “RE but not RECURSIVE”, it...
User Avatar
305
views
1 answers
1 votes
Applied Test Series
The language accepted by the given PDA is
User Avatar
283
views
2 answers
1 votes
can someone share the approach for the following que
14.Show that the grammar S → aSb |SS| e is ambiguous, but that the language denoted by it is not.Can someone share the approach for second part.
User Avatar
719
views
3 answers
2 votes
UGC NET CSE | June 2016 | Part 3 | Question: 56
Let $L=\{0^n1^n|n\ge 0\}$ be a context free language. Which of the following is correct?$\overline L$ is context free and $L^k$ is not context free for any $k\ge1$$\overl...
User Avatar
714
views
1 answers
1 votes
TIFR CSE 2021 | Part B | Question: 5
For a language $L$ over the alphabet $\{a, b\}$, let $\overline{L}$ denote the complement of $L$ and let $L^{\ast}$ denote the Kleene-closure of $L$. Consider the followi...
User Avatar
7.5k
views
2 answers
27 votes
GATE CSE 2021 Set 2 | Question: 41
For a string $w$, we define $w^R$ to be the reverse of $w$. For example, if $w=01101$ then $w^R=10110$.Which of the following languages is/are context-free?$\{ wxw^Rx^R \...
User Avatar
7.7k
views
3 answers
11 votes
GATE CSE 2021 Set 1 | Question: 1
Suppose that $L_1$ is a regular language and $L_2$ is a context-free language. Which one of the following languages is $\text{NOT}$ necessarily context-free?$L_1 \cap L_2...
User Avatar
4.1k
views
2 answers
2 votes
UGC NET CSE | October 2020 | Part 2 | Question: 29
Which of the following statements is true?The union of two context free languages is context freeThe intersection of two context free languages is context freeThe complem...
User Avatar
641
views
1 answers
1 votes
NIELIT 2017 OCT Scientific Assistant A (IT) - Section C: 9
Which of the following definitions generates the same languages as $L,$ where$L = \{x^{n}y^{n},n \geq 1\}$$E \rightarrow xEy \mid xy$$xy \mid x^{+}xyy^{+}$$x^{+}y^{+}$ $(...
User Avatar
651
views
2 answers
1 votes
NIELIT 2017 OCT Scientific Assistant A (CS) - Section B: 31
Which of the following definitions generates the same languages as $L,$ where$L = \{x^{n}y^{n},n \geq 1\}$$E \rightarrow xEy \mid xy$$xy \mid x^{+}xyy^{+}$$x^{+}y^{+}$ $(...
User Avatar
990
views
4 answers
2 votes
NIELIT 2016 MAR Scientist B - Section C: 26
If $L_1$ and $L_2$ are context free language and $R$ a regular set, then which one of the languages below is not necessarily a context free language?$L_1L_2$$L_1\cap L_2$...
User Avatar
794
views
3 answers
2 votes
NIELIT 2016 DEC Scientist B (CS) - Section B: 3
If $L1$ is CFL and $L2$ is regular language which of the following is false?$L1-L2$ is not Context free$L1$ intersection $L2$ is Context free$\sim L1$ is Context freeBoth...
User Avatar
1.6k
views
3 answers
2 votes
NIELIT 2017 DEC Scientist B - Section B: 56
Which of the following statement is true?Deterministic context free language are closed under complement.Deterministic context free language are not closed under Union.De...
User Avatar
1.6k
views
4 answers
3 votes
TIFR CSE 2020 | Part B | Question: 2
Consider the following statements.The intersection of two context-free languages is always context-freeThe super-set of a context-free languages is never regularThe subse...
User Avatar
2.8k
views
4 answers
2 votes
ISRO2020-37
Context free languages are closed underunion, intersectionunion, kleene closureintersection, complementcomplement, kleene closure
User Avatar
Page: