Recent questions tagged context-free-language / GATE Overflow for GATE CSE

0 votes

0 answers

1

Context Free language sample question
Give a context-free grammar for each of the following languages. Consider, Σ={0,1}. A. The language of strings that start with 1 B. The language of strings of the form WWR C. The language of strings that contain the substring 001 D. The language {0n10n where n ≥ 0} E. ... i, j ≥ 0} J. The language {1i01j | j is a multiple of four or i = 3 + 2j where i, j ≥ 0}

Give a context-free grammar for each of the following languages. Consider, Σ={0,1}.A. The language of strings that start with 1B. The language of strings of the form WWR...

dazeeee

48 views

dazeeee asked Apr 3

0 votes

0 answers

2

#toc

Çșȇ ʛấẗẻ

86 views

Çșȇ ʛấẗẻ asked Feb 24

6 votes

1 answer

3

GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 23
Which of the following statements is/are false? If a context-free grammar $\mathrm{G}$ is in Chomsky's normal form, then $\mathrm{G}$ is not ambiguous. For every number $n$ ... s a $10$-state NFA that accepts $\text{L}$ then there's a $100$-state DFA that accepts $\mathrm{L}$.

Which of the following statements is/are false?If a context-free grammar $\mathrm{G}$ is in Chomsky's normal form, then $\mathrm{G}$ is not ambiguous.For every number $n$...

GO Classes

628 views

GO Classes asked Jan 28

7 votes

1 answer

4

GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 56
For a string $x=x_1 \cdots x_n \in \Sigma^*$, where $\Sigma$ is any alphabet and $x_1, \ldots, x_n \in \Sigma$, we write $x^{\uparrow m}=x^m$ (that is, the usual power of strings) and $x^{\downarrow m}=x_1^m \cdots x_n^m$. For empty ... $\left\{(a b c)^{\downarrow n} \mid n \geq 0\right\}$

For a string $x=x_1 \cdots x_n \in \Sigma^*$, where $\Sigma$ is any alphabet and $x_1, \ldots, x_n \in \Sigma$, we write $x^{\uparrow m}=x^m$ (that is, the usual power of...

GO Classes

467 views

GO Classes asked Jan 28

2 votes

1 answer

5

GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 42
Consider the following context-free language: $L_1=\left\{a^m b^n c^n \mid n, m \geq 0\right\}$. Which of the following choices of language $L_2$ is context-free and ensures that $L_1 \cap L_2$ ... and $\left.m \geq 0\right\}$ $L_2=\left\{a^k b^{2 k} c^{2 k} \mid k \geq 0\right\}$

Consider the following context-free language: $L_1=\left\{a^m b^n c^n \mid n, m \geq 0\right\}$. Which of the following choices of language $L_2$ is context-free and ensu...

GO Classes

514 views

GO Classes asked Jan 21

1 votes

1 answer

6

Is it DCFL or CFL?
If it’s DCFL then also construct the DPDA ?

If it’s DCFL then also construct the DPDA ?

vedantk

147 views

vedantk asked Jan 10

2 votes

1 answer

7

ISRO 2024
Which f the following statements is FALSE? The intersection of a regular language and a context-free language is context=free The intersection of a regular language and context-free language is regular The union of two context-free languages is context-free The union of two regular languages is regular

Which f the following statements is FALSE?The intersection of a regular language and a context-free language is context=freeThe intersection of a regular language and con...

Ramayya

179 views

Ramayya asked Jan 7

0 votes

0 answers

8

Can
Can $\Sigma^{*}$ be called DCFL? If yes, what would the state transition diagram of its PDA look like?

Can $\Sigma^{*}$ be called DCFL? If yes, what would the state transition diagram of its PDA look like?

raj_uddeshya157

76 views

raj_uddeshya157 asked Dec 27, 2023

0 votes

1 answer

9

Micheal Sipser 3rd Edition, Problem 2.36
Is the following language context free? $L=\left \{ a^ib^j\:|\: i\neq j\:and\:2i\neq j \right \}$

Is the following language context free?$L=\left \{ a^ib^j\:|\: i\neq j\:and\:2i\neq j \right \}$

rexritz

159 views

rexritz asked Dec 16, 2023

3 votes

2 answers

10

TOC - Self Doubt
Can anyone explain $\overline{ww}$ is $CFL$ or $CSL$ And if $CFL$ can you write the equivalent $CFG$ for this ?

Can anyone explain $\overline{ww}$ is $CFL$ or $CSL$ And if $CFL$ can you write the equivalent $CFG$ for this ?

Jiten008

357 views

Jiten008 asked Oct 24, 2023

1 votes

2 answers

11

Unacademy Compiler Design Workbook
Consider the following statements: (A) LL (k) grammars have one to one correspondence with DCFLs. (B) LR (k) grammars have one to one correspondence with CFLs. A is true but B is false A is false but B is true Both are False Both are True

Consider the following statements:(A) LL (k) grammars have one to one correspondence with DCFLs.(B) LR (k) grammars have one to one correspondence with CFLs. A is true bu...

lovish_bhatia

362 views

lovish_bhatia asked Sep 12, 2023

1 votes

1 answer

12

Self Doubt from GoClasses Test Series
If L= { a^p | where p is any prime number }, then what is:- i) L+ ii) L* iii)L^3

If L= { a^p | where p is any prime number }, then what is:- i) L+ ii) L*iii)L^3

Swarnava Bose

271 views

Swarnava Bose asked Aug 26, 2023

0 votes

1 answer

13

General Doubt
Convert this language to Push Down Automata – {a^n u | u ∈ {a, b}*, |u| = n, n ≥ 0}

Convert this language to Push Down Automata – {a^n u | u ∈ {a, b}*, |u| = n, n ≥ 0}

Shaina Singh

223 views

Shaina Singh asked Jul 31, 2023

1 votes

1 answer

14

PDA,DCFL and CFL

Sourin Kundu

234 views

Sourin Kundu asked Jul 4, 2023

0 votes

1 answer

15

Theory of Computation

gateexplore

158 views

gateexplore asked Jul 2, 2023

0 votes

1 answer

16

Theory of Computation
Find a Greibach normal form grammar equivalent to the following CFG. S →ASB/ AB A→ a B → b

Find a Greibach normal form grammar equivalent to the following CFG.S →ASB/ ABA→ aB → b

gateexplore

332 views

gateexplore asked Jun 23, 2023

1 votes

1 answer

17

toc
$a^{p}b^{p}a^{p} where p>=0$ can i write this lang. as cfl when a come push in to the stack when b skip all b’s again when a pop all the a from the stack …..

$a^{p}b^{p}a^{p} where p>=0$ can i write this lang. as cfl when a come push in to the stack when b skip all b’s again when a pop all the a from the stack …..

jugnu1337

362 views

jugnu1337 asked Apr 16, 2023

0 votes

1 answer

18

Theory of computation

Manukumr

243 views

Manukumr asked Apr 8, 2023

1 votes

1 answer

19

Context Free Language
The complement of the languages: i) {ww | w in (0+1)*} ii) {$a^n b^nc^n$ | n>1} are a) Context Free b) Not Context Free c)are DCFL’s d)None

The complement of the languages:i) {ww | w in (0+1)*}ii) {$a^n b^nc^n$ | n>1} area) Context Free b) Not Context Free c)are DCFL’s d)None

practicalmetal

368 views

practicalmetal asked Mar 20, 2023

0 votes

1 answer

20

Context Free Languages
Is the following language CFL : { ww | w in (a+b)* and |w| <1000 }

Is the following language CFL :{ ww | w in (a+b)* and |w| <1000 }

practicalmetal

551 views

practicalmetal asked Mar 20, 2023

0 votes

1 answer

21

Context Free Languages
Is the following language context free: The set of all strings with number of a’s equal to number of b’s and the sum of a’s and b’s to be divisible by 3.

Is the following language context free:The set of all strings with number of a’s equal to number of b’s and the sum of a’s and b’s to be divisible by 3.

practicalmetal

513 views

practicalmetal asked Mar 15, 2023

0 votes

0 answers

22

#TIFR
Consider the language $L = \{a^i \$ a^j \$ b^k \$ | k ⩽ max(i, j), i, j, k ≥ 0\}$ over the alphabet $\sum = \{a, b, \$ \}$. The complement of the language L, that is, $\sum^* - \text{ L}$ is denoted by $L'$. Which of the following is ... d) $L$ is a context-free language and $L'$ is not a context-free language. (e) Neither is $L$ a context-free language nor is $L'$ a context-free language.

Consider the language $L = \{a^i \$ a^j \$ b^k \$ | k ⩽ max(i, j), i, j, k ≥ 0\}$ over the alphabet $\sum = \{a, b, \$ \}$. The complement of the language L, that is,...

amit166

367 views

amit166 asked Feb 13, 2023

0 votes

2 answers

23

context free grammar
what is the langauge generated by this grammar ? S-->aS | aSbS | ε what is the language

what is the langauge generated by this grammar ?S >aS | aSbS | ε what is the language

moe12leb

268 views

moe12leb asked Jan 21, 2023

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