Recent questions tagged context-free-language

0 votes

0 answers

1

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 in Theory of Computation by rahuljai (43 points) | 36 views

+2 votes

1 answer

2

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 in Theory of Computation by Prince Sindhiya Active (5.2k points) | 59 views

0 votes

2 answers

3

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

asked Nov 1 in Theory of Computation by Shamim Ahmed Junior (935 points) | 83 views

0 votes

0 answers

4

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

asked Nov 1 in Theory of Computation by Shamim Ahmed Junior (935 points) | 39 views

0 votes

1 answer

5

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 in Theory of Computation by saptarshiDey (37 points) | 27 views

0 votes

0 answers

6

Ace Book

asked Oct 28 in Theory of Computation by abhishek1995_cse (159 points) | 49 views

0 votes

1 answer

7

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

asked Oct 23 in Theory of Computation by aditi19 Active (2k points) | 23 views

0 votes

1 answer

8

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 in Theory of Computation by abhishek1995_cse (159 points) | 53 views

0 votes

0 answers

9

Ace Book
The complement of the language L containing an equal number of a's , b's and c's is a)regular b)context free c)context sensitive but not context free d)recursive and not a CFL

asked Oct 21 in Theory of Computation by abhishek1995_cse (159 points) | 38 views

0 votes

0 answers

10

Context Free Grammar
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

asked Oct 18 in Theory of Computation by Sambhrant Maurya Junior (947 points) | 34 views

0 votes

1 answer

11

Theory of Computation
$L1= \left \{ a^m b^n c^n d^m | m \neq n \right \}$ $L2= \left \{a^i b^j c^k | (i<=j)or (j<=i), j=k \right \}$ $L3= \left \{a^i b^j c^k| i=j, j<k \right \}$ The number of the above languages that are context free are ?

asked Oct 18 in Theory of Computation by Priyam Pandey (111 points) | 94 views

0 votes

0 answers

12

CFL with Empty Stack or Final State
$1)$"We can solve same PDA with empty stack and using final state" Can give an example of such language? Where is the difference between solving a pda with empty stak and by accepting final state? I got this link but without ... -acceptance-by-empty-stack-and-final-state $2)$If language has prefix property, why it cannot be solved with empty stack?

asked Oct 4 in Theory of Computation by srestha Veteran (103k points) | 82 views

0 votes

0 answers

13

self doubt
name and explain the language which are context free,context sensitive i.e. FORTRAN is CSL, now tell me about c,cobol,c++,java and any other language which you can explain etc https://gateoverflow.in/80293/gate1987-1-xiii

asked Sep 30 in Theory of Computation by Gurdeep Saini Active (5k points) | 18 views

0 votes

0 answers

14

CFG-Doubt
$L=a^mb^nc^pd^q | m+p=n+q, m,n,p,q>=0$ is the language CFG or CFL?

asked Sep 26 in Theory of Computation by aditi19 Active (2k points) | 34 views

0 votes

0 answers

15

Context free languages
X belongs to {a,b}* such that n(a)<n(b)<2n(a) is a CFL. Please somebody explain the push and pop sequences of the alphabets on the stack. I'm not being able to visualise, how it is CFL?

asked Sep 18 in Theory of Computation by aambazinga Active (1.8k points) | 21 views

+1 vote

0 answers

16

Michael sipser
I read this excerpt from sipser book- We write a,b → c to signify that when the machine is reading an a from the input, it may replace the symbol b on the top of the stack with a c. Any of a, b, and c may be ε. If a is ε, the machine ... using any stack symbol as written here that top of stack might be epsilon if we don't want to consume it. If someone can clear my doubt. Thanks

asked Sep 15 in Theory of Computation by sushmita Boss (15.2k points) | 12 views

0 votes

0 answers

17

Closure Property
If L1 is CSL and L2 is CFL, then which of the following is correct ? A.L1' - L2 is CSL always B. L1 - L2' is CSL always C. L1 intersection Regular is Regular always D. L1.L2 is CSL but not CFL

asked Sep 9 in Theory of Computation by Na462 Loyal (7.4k points) | 76 views

0 votes

0 answers

18

peter linz
The language L1={a^n b^n} union {b} The language L2={a^n b^n} union {a} They both are deterministic CFL. Am i right?

asked Sep 9 in Theory of Computation by sushmita Boss (15.2k points) | 38 views

0 votes

0 answers

19

self doubt
Consider the Context free language which has equal no of as and bs. eg- abab Since a proper prefix ab also belongs to this language, this language does not satisfy prefix property as far as i understand. But we can clearly draw a deterministic PDA ... with empty stack for CFL without prefix property. But above example forms a contradiction. Please resolve my doubt. I am getting confused.

asked Sep 8 in Theory of Computation by sushmita Boss (15.2k points) | 56 views

0 votes

0 answers

20

PDA-Doubt
L=$a^mb^n$ | m!=n is the following DPDA correct for the mentioned language?

asked Sep 3 in Theory of Computation by aditi19 Active (2k points) | 26 views

0 votes

0 answers

21

Doubt-PDA
what is the PDA for {L=$a^mb^n$ |m>n}

asked Sep 2 in Theory of Computation by aditi19 Active (2k points) | 76 views

0 votes

1 answer

22

Non inherently ambiguous

asked Sep 2 in Theory of Computation by Na462 Loyal (7.4k points) | 53 views

0 votes

0 answers

23

Parsing
For a grammar to be LR(k), it should have a PDA? Like a DPDA or just PDA in general?

asked Aug 31 in Compiler Design by Mizuki Active (1k points) | 44 views

0 votes

0 answers

24

DPDA acceptance by empty stack
Is this approach of acceptance by empty stack correct ? I am confused because i have read that acceptance by empty stack may not be able to accept all regular languages.

asked Jul 28 in Theory of Computation by Matrix (67 points) | 72 views

+1 vote

2 answers

25

Languages
Consider a language over Σ={a,b} the description of L is given below. L={ PQ | P ∈(a,b)* , Q ∈ (a,b)* and na(P) = nb(Q) }. Select the correct option. 1. L is DCFL but not regular. 2. L is CSL but not CFL. 3. L is CFL but not DCFL. 4. None of these.

asked Jul 3 in Theory of Computation by Priyansh Singh (263 points) | 113 views

0 votes

1 answer

26

self made doubt
How to know that the language needs 1 stack or more than one stack in order to know about it is regular, context-free or not. example L1={$a^i b^j c^k│i<j<k$} L2={$a^i b^j c^k│i<j \ or \ k<j$} L3={$a^i b^j c^k│i<j \ and \ k<j$}

asked Jun 11 in Theory of Computation by Divyanshum29 Junior (747 points) | 69 views

0 votes

2 answers

27

Theory Of Computation Doubt.
I saw some where that a language which accepts $a^{n^{2}} | n \geq1$ is not context free Language and not regular language. is it not a language that has at least one $'a'$ as the string?. It should be regular as well according to this Logic right. Please correct me if wrong.

asked Jun 3 in Theory of Computation by abhiram144 (63 points) | 56 views

0 votes

2 answers

28

Ambiguous and unambiguous grammar
If a grammar( $CFG$ ) has more than one Right most derivation, Can it be called ambiguous ? Or we say a grammar is ambiguous only when it has more than one left most derivation ?

asked May 28 in Compiler Design by Rahul Ranjan 1 (151 points) | 87 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