Recent questions tagged context-free-languages - GATE CSE Doubts

+1 vote

2 answers

#toc #self_doubts #cfl
$L={\;\{\;a^{(m+n)}b^{(m+k)}c^{(k+n)}}, m,n,k ≥ 0 \;\}$ $L$ is CFL or DCFL? My logic is push all $a’s$ and then pop $m$ $b’s$ and push $k$ $b’s$, so here we need non determinism, so it should be CFL and not DCFL. Can anyone design a DPDA for it?

asked Sep 2, 2020 in Theory of Computation by suvradip das (119 points) | 344 views

0 votes

1 answer

Chomsky Classification
which grammars of Chomsky Classification allows (S → ε) in its production rules ?

asked Aug 19, 2020 in Theory of Computation by Akshay sinha (9 points) | 42 views

+1 vote

2 answers

Self Doubt Peter Linz 5th edition: Exercise 8.1, Q13 [CFL Pumping Lemma]

asked Aug 16, 2020 in Theory of Computation by pritishc (23 points) | 47 views

0 votes

0 answers

TOC(self doubt-classification into the language)
Came to read and also got to know as a shortcut about classification of a Language on the basis of the comparisons into CFL or CSL.Is it really the standard method or is it the short trick or just an ill-defined way of attempting a question. This post can be taken as a reference – https://gateoverflow.in/26952/%23toc

asked Jul 13, 2020 in Theory of Computation by prajjwalsingh_11 (15 points) | 14 views

0 votes

1 answer

Context Free Language
Is this CFL? L = {wcwr | w, c ϵ {0,1}+ and |c| = 2}

asked Jul 1, 2020 in Theory of Computation by sameer2009 (5 points) | 17 views

+1 vote

1 answer

pushdown automata #CFL
Is the following language context-free language(CFL) or not? If yes, then is it Deterministic-CFL (DCFL)? L={ $a^i b^j$ where $i\neq 2*j+1$ and $j \geq 1$ and $i\geq 1$ }

asked Jun 28, 2020 in Theory of Computation by rgoyal (11 points) | 50 views

0 votes

0 answers

Peter Linz Exercise-8.2 Context Free Lnaguages
Show that the following language is context free L={$w\epsilon (a, b)$* : $n_{a}(w)=n_{b}(w)$, w does not contain the substring aab}

asked Jun 16, 2020 in Theory of Computation by aditi19 (43 points) | 20 views

0 votes

0 answers

Peter Linz Theory of Computation Exercise 5.1 Question-15

asked Jun 11, 2020 in Theory of Computation by aditi19 (43 points) | 24 views

0 votes

0 answers

GATE2018-35 Video Solution
Consider the following languages: $\{a^mb^nc^pd^q \mid m+p=n+q, \text{ where } m, n, p, q \geq 0 \}$ $\{a^mb^nc^pd^q \mid m=n \text{ and }p=q, \text{ where } m, n, p, q \geq 0 \}$ ... Which of the above languages are context-free? I and IV only I and II only II and III only II and IV only

asked Apr 18, 2020 in Theory of Computation by admin (573 points) | 8 views

0 votes

0 answers

GATE2016-1-42 Video Solution
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$ Which one of the following pairs of languages is generated by $G_1$ and $G_2$ ... $\{ a^mb^n \mid m > 0 \text{ or } n>0\}$

asked Apr 18, 2020 in Theory of Computation by admin (573 points) | 11 views

0 votes

0 answers

GATE2017-1-10 Video Solution
Consider the following context-free grammar over the alphabet $\Sigma = \{a,b,c\}$ with $S$ as the start symbol:$S \rightarrow abScT \mid abcT$$T \rightarrow bT \mid b$ ... $\{\left ( ab \right )^{n}\left ( cb^{n} \right )^{m} \mid m,n \geq 1 \}$

asked Apr 18, 2020 in Theory of Computation by admin (573 points) | 4 views

0 votes

0 answers

GATE2015-3-32 Video Solution
Which of the following languages are context-free? $L_1: \left\{a^mb^na^nb^m \mid m, n \geq 1\right\}$ $L_2: \left\{a^mb^na^mb^n \mid m, n \geq 1\right\}$ $L_3: \left\{a^mb^n \mid m = 2n +1 \right\}$ $L_1$ and $L_2$ only $L_1$ and $L_3$ only $L_2$ and $L_3$ only $L_3$ only

asked Apr 18, 2020 in Theory of Computation by admin (573 points) | 7 views

0 votes

0 answers

GATE2003-51 Video Solution
Let $G=\left(\left\{S\right\}, \left\{a,b\right\},R,S\right)$ be a context free grammar where the rule set R is $S \to a S b \mid S S \mid \epsilon$ Which of the following statements is true? $G$ is not ambiguous There ... $L(G)$ We can find a deterministic finite state automaton that accepts $L(G)$

asked Apr 18, 2020 in Theory of Computation by admin (573 points) | 3 views

0 votes

0 answers

GATE2009-12, ISRO2016-37 Video Solution
$S \to aSa \mid bSb\mid a\mid b$ The language generated by the above grammar over the alphabet $\{a,b\}$ is the set of: all palindromes all odd length palindromes strings that begin and end with the same symbol all even length palindromes

asked Apr 18, 2020 in Theory of Computation by admin (573 points) | 5 views

0 votes

0 answers

GATE2016-1-16 Video Solution
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\text{ has equal number of a's and b's}\}$ $\{a^n \mid n \geq 0 \} \cup \{b^n \mid n \geq 0\} \cup \{a^n b^n \mid n \geq 0\}$ $\{ a,b\}^*$

asked Apr 18, 2020 in Theory of Computation by admin (573 points) | 5 views

0 votes

0 answers

GATE2017-1-38 Video Solution
Consider the following languages over the alphabet $\sum = \left \{ a, b, c \right \}$. Let $L_{1} = \left \{ a^{n}b^{n}c^{m}|m,n \geq 0 \right \}$ and $L_{2} = \left \{ a^{m}b^{n}c^{n}|m,n \geq 0 \right \}$. Which of the following are context-free languages? $L_{1} \cup L_{2}$ $L_{1} \cap L_{2}$ I only II only I and II Neither I nor II

asked Apr 18, 2020 in Theory of Computation by admin (573 points) | 9 views

0 votes

0 answers

GATE2016-2-43 Video Solution
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? Both $L_{1}$ and $L_{2}$ are context-free. $L_{1}$ is context- ... $L_{2}$ is context-free while $L_{1}$ is not context-free. Neither $L_{1}$ nor $L_{2}$ is context-free.

asked Apr 18, 2020 in Theory of Computation by admin (573 points) | 8 views

0 votes

0 answers

GATE2017-1-37 Video Solution
Consider the context-free grammars over the alphabet $\left \{ a, b, c \right \}$ given below. $S$ and $T$ are non-terminals. $G_{1}:S\rightarrow aSb \mid T, T \rightarrow cT \mid \epsilon$ ... is Finite Not finite but regular Context-Free but not regular Recursive but not context-free

asked Apr 18, 2020 in Theory of Computation by admin (573 points) | 6 views

0 votes

0 answers

GATE2007-IT-49 Video Solution
Consider the following grammars. Names representing terminals have been specified in capital letters. $\begin{array}{llll}\hline \text{$G1$ :} & \text{stmnt} & \text{$ ... $G_1$ and $G_2$ are regular Both $G_1$ and $G_2$ are context-free but neither of them is regular

asked Apr 18, 2020 in Theory of Computation by admin (573 points) | 16 views

0 votes

0 answers

GATE2016-2-18 Video Solution
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 TRUE ? $\overline{L_{3}} \cup L_{4}$ is recursively enumerable. $\overline{L_{2}} \cup L_{3}$ ... $L_{1} \cup \overline{L_{2}}$ is context-free. I only. I and III only. I and IV only. I, II and III only.

asked Apr 18, 2020 in Theory of Computation by admin (573 points) | 6 views

0 votes

0 answers

GATE1996-2.9 Video Solution
Define a context free languages $L \in \{0, 1\}^*$, $\text{init} (L) = \{u \mid uv \in L$ for some $v$ in $\{0, 1\}^*\}$ ( in other words, $\text{init}(L)$ is the set of prefixes of $L$ ... string the set of all binary strings with exactly one more $0$ than the number of $1$'s or one more $1$ than the number of $0$'s None of the above

asked Apr 18, 2020 in Theory of Computation by admin (573 points) | 9 views

0 votes

0 answers

GATE2010-40 Video Solution
Consider the languages $L1=\{0^i1^j\ \mid i \neq j\}, $ $L2=\{0^i1^j\mid i=j\},$ $L3=\{0^i1^j \mid i=2j+1\},$ $L4=\{0^i1^j \mid i\neq2j\}$ Only $L2$ is context free. Only $L2$ and $L3$ are context free. Only $L1$ and $L2$ are context free. All are context free

asked Apr 18, 2020 in Theory of Computation by admin (573 points) | 4 views

0 votes

0 answers

GATE2006-19 Video Solution
Let $L_1=\{0^{n+m}1^n0^m\mid n,m\geq 0 \}$, $L_2=\{0^{n+m}1^{n+m}0^m\mid n,m\geq 0\}$ and $L_3=\{0^{n+m}1^{n+m}0^{n+m}\mid n,m\geq 0\} $. Which of these languages are NOT context free? $L_1$ only $L_3$ only $L_1$ and $L_2$ $L_2$ and $L_3$

asked Apr 18, 2020 in Theory of Computation by admin (573 points) | 7 views

0 votes

0 answers

GATE1992-02,xviii Video Solution
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: If $G$ is a context free grammar and $w$ is a string of length $l$ in $L(G)$, how long is a derivation of $w$ in $G$, if $G$ is in Chomsky normal form? $2l$ $2l +1$ $2l -1$ $l$

asked Apr 18, 2020 in Theory of Computation by admin (573 points) | 11 views

0 votes

0 answers

GATE2017-2-16 Video Solution
Identify the language generated by the following grammar, where $S$ is the start variable. $ S \rightarrow XY$ $ X \rightarrow aX \mid a$ $ Y \rightarrow aYb \mid \epsilon$ $\{a^mb^n \mid m \geq n, n > 0 \}$ $ \{ a^mb^n \mid m \geq n, n \geq 0 \}$ $\{a^mb^n \mid m > n, n \geq 0 \}$ $\{a^mb^n \mid m > n, n > 0 \}$

asked Apr 18, 2020 in Theory of Computation by admin (573 points) | 7 views

0 votes

0 answers

GATE2019-31 Video Solution
Which one of the following languages over $\Sigma=\{a, b\}$ is NOT context-free? $\{ww^R \mid w \in \{a, b\}^*\}$ $\{wa^nb^nw^R \mid w \in \{a,b\}^*, n \geq 0\}$ $\{wa^nw^Rb^n \mid w \in \{a,b\}^* , n \geq 0\}$ $\{ a^nb^i \mid i \in \{n, 3n, 5n\}, n \geq 0\}$

asked Apr 18, 2020 in Theory of Computation by admin (573 points) | 10 views

0 votes

0 answers

GATE2017-1-34 Video Solution
If $G$ is a grammar with productions $S\rightarrow SaS\mid aSb\mid bSa\mid SS\mid\epsilon$ where $S$ is the start variable, then which one of the following strings is not generated by $G$? $abab$ $aaab$ $abbaa$ $babba$

asked Apr 18, 2020 in Theory of Computation by admin (573 points) | 6 views

0 votes

0 answers

GATE2008-IT-34 Video Solution
Consider a CFG with the following productions. $S \to AA \mid B$ $A \to 0A \mid A0 \mid 1$ $B \to 0B00 \mid 1$ $S$ is the start symbol, $A$ and $B$ ... $\{0, 1\}$ containing at least two $0$'s

asked Apr 18, 2020 in Theory of Computation by admin (573 points) | 6 views

0 votes

0 answers

GATE2014-3-35 Video Solution
Which one of the following problems is undecidable? Deciding if a given context-free grammar is ambiguous. Deciding if a given string is generated by a given context-free grammar. Deciding if the language generated by a given context-free grammar is empty. Deciding if the language generated by a given context-free grammar is finite.

asked Apr 18, 2020 in Theory of Computation by admin (573 points) | 6 views

0 votes

0 answers

GATE2008-IT-79 Video Solution
$A$ CFG $G$ is given with the following productions where $S$ is the start symbol, $A$ is a non-terminal and a and b are terminals. $S → aS \mid A$ $A → aAb \mid bAa \mid \epsilon$ For the string "$aabbaab$" how many steps are required to derive the string and how many parse trees are there? $6$ and $1$ $6$ and $2$ $7$ and $2$ $4$ and $2$

asked Apr 18, 2020 in Compiler Design by admin (573 points) | 6 views

0 votes

0 answers

GATE2008-IT-78 Video Solution
A $CFG$ $G$ is given with the following productions where $S$ is the start symbol, $A$ is a non-terminal and $a$ and $b$ are terminals. $S \to aS \mid A$ $A \to aAb \mid bAa \mid \epsilon$ Which of the following strings is generated by the grammar above? $aabbaba$ $aabaaba$ $abababb$ $aabbaab$

asked Apr 18, 2020 in Theory of Computation by admin (573 points) | 4 views

0 votes

0 answers

GATE2001-1.5 Video Solution
Which of the following statements is true? If a language is context free it can always be accepted by a deterministic push-down automaton The union of two context free languages is context free The intersection of two context free languages is a context free The complement of a context free language is a context free

asked Apr 18, 2020 in Theory of Computation by admin (573 points) | 15 views

0 votes

0 answers

GATE1999-1.5 Video Solution
Context-free languages are closed under: Union, intersection Union, Kleene closure Intersection, complement Complement, Kleene closure

asked Apr 18, 2020 in Theory of Computation by admin (573 points) | 12 views

0 votes

0 answers

GATE1995-2.20 Video Solution
Which of the following definitions below generate the same language as $L$, where $L=\{x^ny^n \text{ such that } n\geq 1 \}$? $E \rightarrow xEy\mid xy$ $x y \mid (x^+xyy^+$) $x^+y^+$ I only I and II II and III II only

asked Apr 18, 2020 in Theory of Computation by admin (573 points) | 12 views

0 votes

0 answers

GATE2014-3-36 Video Solution
Consider the following languages over the alphabet $\sum = \{0, 1, c\}$ $L_1 = \left\{0^n1^n\mid n \geq 0\right\}$ $L_2 = \left\{wcw^r \mid w \in \{0,1\}^*\right\}$ ... of the string $w$. Which of these languages are deterministic Context-free languages? None of the languages Only $L_1$ Only $L_1$ and $L_2$ All the three languages

asked Apr 18, 2020 in Theory of Computation by admin (573 points) | 5 views

0 votes

0 answers

GATE2007-IT-48 Video Solution
Consider the grammar given below: $S \rightarrow x \ B \mid y \ A$ $A \rightarrow x \mid x \ S \mid y \ A \ A$ $B \rightarrow y \mid y \ S \mid x \ B \ B$ Consider the following strings. $xxyyx$ $xxyyxy$ $xyxy$ $yxxy$ $yxx$ $xyx$ Which of the above strings are generated by the grammar ? i, ii and iii ii, v and vi ii, iii and iv i, iii and iv

asked Apr 18, 2020 in Theory of Computation by admin (573 points) | 3 views

0 votes

0 answers

GATE2005-57 Video Solution
Consider the languages: $L_1 = \left\{ww^R \mid w \in \{0, 1\}^* \right\}$ $L_2 = \left\{w\text{#}w^R \mid w \in \{0, 1\}^* \right\}$, where $\text{#}$ ... of the following is TRUE? $L_1$ is a deterministic CFL $L_2$ is a deterministic CFL $L_3$ is a CFL, but not a deterministic CFL $L_3$ is a deterministic CFL

asked Apr 18, 2020 in Theory of Computation by admin (573 points) | 5 views

0 votes

0 answers

GATE1996-2.8 Video Solution
If $L_1$ and $L_2$ are context free languages and $R$ a regular set, one of the languages below is not necessarily a context free language. Which one? $L_1.L_2$ $L_1 \cap L_2$ $L_1 \cap R$ $L_1 \cup L_2$

asked Apr 18, 2020 in Theory of Computation by admin (573 points) | 5 views

0 votes

0 answers

GATE2007-IT-46 Video Solution
The two grammars given below generate a language over the alphabet $\{x, y, z\}$ $G1 : S \rightarrow x \mid z \mid x \ S \mid z \ S \mid y \ B$ $B \rightarrow y \mid z \mid y \ B \mid z \ B$ ... Every $x$ is followed by at least one $y$ $G1$ : No $y$ appears after any $x$ $G2$ : Every $y$ is followed by at least one $x$

asked Apr 18, 2020 in Theory of Computation by admin (573 points) | 4 views

0 votes

0 answers

GATE2006-IT-34 Video Solution
In the context-free grammar below, $S$ is the start symbol, $a$ and $b$ are terminals, and $\epsilon$ denotes the empty string. $S \to aSAb \mid \epsilon$ $A \to bA \mid \epsilon$ The grammar generates the language $((a + b)^* b)$ $\{a^mb^n \mid m \leq n\}$ $\{a^mb^n \mid m = n)$ $a^* b^*$

asked Apr 18, 2020 in Theory of Computation by admin (573 points) | 15 views

Page:

8,998 questions

3,130 answers

14,378 comments

95,816 users