Recent questions tagged context-free-language

0 votes

3 answers

1

GATE2019-31
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 Feb 7 in Theory of Computation by Arjun Veteran (385k points) | 1.5k views

0 votes

0 answers

2

Consider a language L = {xaybzc| ((a ≤ b) or (a > b)) and (a ≠ c)}. Select the correct option.

asked Jan 28 in Theory of Computation by AVICS (7 points) | 44 views

0 votes

2 answers

3

language
ϕ Σ* L X

asked Jan 22 in Theory of Computation by Rahul_Rathod_ Junior (565 points) | 69 views

0 votes

1 answer

4

TOC: CFG to GNF
$S->AA|0$ $A->SS|1$ Can someone please help to convert this CFG into Greiback normal formal (GNF)?

asked Jan 22 in Theory of Computation by chauhansunil20th Active (4.8k points) | 33 views

0 votes

0 answers

5

A language is cfl or not
L = {a^(p+q) b^(p+q) a^p , p,q>=0} Which one of the following is true about L? L is a regular L is CFL but not regular L is not a CFL

asked Jan 22 in Theory of Computation by saptarshiDey (83 points) | 21 views

0 votes

1 answer

6

Context Free Languages
What is the difference between regular intersection and intersection? (I found out that CFL is closed under regular intersection but not under intersection) Thanks!

asked Jan 22 in Theory of Computation by Abhipsa Mishra (149 points) | 19 views

+1 vote

1 answer

7

Context free language
Is this a deterministic context free language (DCFL) ? $a^{k}$ | k is even Thanks!

asked Jan 22 in Theory of Computation by Abhipsa Mishra (149 points) | 23 views

0 votes

1 answer

8

Cfg to and from pda
Do i have to study the conversation of pda to Cfg or cfg to pda? Is this an important concept with relevance to gate? I know how to individually make them though.

asked Jan 21 in Theory of Computation by Rhythm (75 points) | 29 views

0 votes

0 answers

9

CFL or CSL
Let L = $\{ a^n b^m | m , n \in \textbf{N} \text{ and m is multiple of n}\}$ How do we prove that this language is not CFL.

asked Jan 18 in Theory of Computation by !KARAN Active (1.2k points) | 23 views

0 votes

0 answers

10

Building a pushdown automata that receives L*
given a pushdown automata that receives L by getting to an accepting state, how can a pushdown automata be built, so that it accepts L*? (might use a “double bottom” if needed)?? i don’t know how to solve it and would appreciate any kind of help! studying for exam and must learn how to solve it

asked Jan 16 in Theory of Computation by agmund (7 points) | 21 views

0 votes

1 answer

11

Test Series
If $L_1$ is DCFL and $L_2$ is context free language. Consider the below given statements Which is correct between these and why ? (S1 is correct.. but why ??) . I couldn’t understand the explanation given in the solution..

asked Jan 14 in Theory of Computation by Hardik Maheshwari (97 points) | 47 views

0 votes

0 answers

12

Made Easy test series
L1 is regular, L2 and L3 are CFL L1 is regular, L2 is CFL and L3 is CSL L1 is CFL but not regular,L2 is CSL but not CFL,L3 is CFL L1, L2 and L3 are CFL

asked Jan 9 in Theory of Computation by Sambhrant Maurya Active (1.5k points) | 37 views

0 votes

0 answers

13

Context free languages
{x w c w1, where x,w belong to {a,b}* and w1 is reverse of w} The language given is deterministic context-free language or non-deterministic context-free language?

asked Jan 8 in Theory of Computation by Iamniks4 (63 points) | 22 views

0 votes

0 answers

14

DCFL or CFL?
Given that: { A^m B^n C^k/ if (k=even) then m=n} { A^m B^n C^k/ if (n=even) then m=k} Which of the above languages are DCFL? According to me it is CFL as we have to first count k and then compare other inputs.. same for second language ... is both are DCFL? it is only possible if skip path is exists here? does it exist for DCFLs? so confused please guide me? if given answer is correct?

asked Jan 3 in Theory of Computation by S Ram Active (1.9k points) | 121 views

0 votes

1 answer

15

Madeasy test series
Does equivalence of CFG decidable ? That is for two CFG G1 and G2 L(G1)= L(G2)? And if it is DCFG than is it decidable.

asked Dec 30, 2018 in Theory of Computation by Ayan21 (107 points) | 53 views

0 votes

0 answers

16

context free grammer
consider following grammer S → aSb / aSbb / aSbbb / ….. is language generated by above grammer is DCFL?

asked Dec 24, 2018 in Theory of Computation by Rahul_Rathod_ Junior (565 points) | 52 views

0 votes

1 answer

17

Context free language Question
please provide solution for given quesion.

asked Dec 16, 2018 in Theory of Computation by Dharmesh Gusai 1 (141 points) | 39 views

+1 vote

0 answers

18

CONVERT CFG TO GNF
S→ AB A→ BS|b B→ SA|a INTO GNF

asked Dec 14, 2018 in Theory of Computation by Menon Karthik (41 points) | 64 views

+1 vote

1 answer

19

TOC Which is(are) regular? Please explain 1 and 4.
Which of the following languages is regular? L = { bba (ba)* a^n-1 | n> 0 } L = {a^nb^n | n < 1000 } L = {a^nb^k | n is odd or k is even } L = {wxw^R | w,x ∈(0+1)* } 1, 3 and 4 2, 3, 4 2, 3 1, 2, 3, 4

asked Dec 13, 2018 in Theory of Computation by rahuljai (437 points) | 99 views

0 votes

0 answers

20

Draw PDA for this
L = {a^m b^n c^k=m+n } | m >= 0 and n >= 0 ---------------------- Please draw PDA for this Language!

asked Dec 12, 2018 in Theory of Computation by Guilherme Zanini Mor (9 points) | 49 views

0 votes

0 answers

21

TOC - PDA
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 by rahuljai (437 points) | 58 views

+2 votes

1 answer

22

gate zeal test TOC
select the correct statement Non-CFL is closed under reversal operation . L=$ \{ \;0^n1^m0^m: n+m \; mod \;6 =2 \} $ is CFL but not regular. if L is context free and R and S are regular ,then MAJORITY(L,R,S)={ w| w is in atleast two of R,L,S } is also context free (a) only i (b) only I and II (c) Only II and III (d) All

asked Nov 25, 2018 in Theory of Computation by Prince Sindhiya Loyal (6.2k points) | 77 views

0 votes

2 answers

23

Decidability
Given two deterministic CFG G$_1$ and G$_2$, is L( G$_1$ ) = L( G$_2$ ) ?

asked Nov 1, 2018 in Theory of Computation by Shamim Ahmed Active (2.3k points) | 99 views

0 votes

0 answers

24

Decidability
Given two deterministic CFG G$_1$ and G$_2$ , is L(G$_1$) ∩ L(G$_2$) = ∅ ?

asked Nov 1, 2018 in Theory of Computation by Shamim Ahmed Active (2.3k points) | 54 views

0 votes

1 answer

25

Complementation of a Language of a L
If L is any Language and L' be its complement. L is CFL. Which of these two statements is true: 1. For any value of L, L' is not in CFL 2. There exists atleast one value of L for which L' is not in CFL

asked Oct 31, 2018 in Theory of Computation by saptarshiDey (83 points) | 39 views

0 votes

0 answers

26

Ace Book

asked Oct 28, 2018 in Theory of Computation by abhishek1995_cse (169 points) | 60 views

0 votes

1 answer

27

Context Free Grammar
L=0^i 1^j 2^k | i=j or j=k is the grammar DCFG?

asked Oct 23, 2018 in Theory of Computation by aditi19 Active (2.3k points) | 26 views

0 votes

1 answer

28

Ace book
The minimal finite automata accepting the set of all strings over {0,1} starting with a 1 that interpreted as the binary representation of an integer are congruent to 0 modulo 5 has ______ states. The ans is 7 but according to me modulo n has 5 states .?

asked Oct 22, 2018 in Theory of Computation by abhishek1995_cse (169 points) | 66 views

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true

Recent questions tagged context-free-language

Recent Posts

Recent Blog Comments