The Gateway to Computer Science Excellence
0 votes
13 views

Let $CFG$   $G$ be the following grammar$.$

  •  $S\rightarrow aSb \mid bY \mid Y a$
  • $Y\rightarrow bY \mid aY \mid \epsilon$

Give a simple description of $L(G)$ in English$.$ Use that description to give a $CFG$ for $\overline{L(G)},$ the complement of $L(G).$

in Theory of Computation by Veteran (53k points)
edited by | 13 views
0
L(G)=$a^nxb^n$ | $x\epsilon (a|b)^+$

Please log in or register to answer this question.

Related questions

Quick search syntax
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
50,654 questions
56,169 answers
193,876 comments
94,298 users