Optimal Lower Bounds on Regular Expression Size using Communication Complexity
Optimal Lower Bounds on Regular Expression Size using Communication Complexity
Hermann Gruber and Jan Johannsen
Institut f¨u r Informatik,LMU M¨u nchen
Oettingenstr.67,80538M¨u nchen,Germany
[gruberh|jjohanns]@tcs.ifi.lmu.de
Abstract.The problem of converting deterministic?nite automata into
(short)regular expressions is considered.It is known that the required
expression size is2Θ(n)in the worst case for in?nite languages,and for
?nite languages it is n?(log log n)and n O(log n),if the alphabet size grows
with the number of states n of the given automaton.A new lower bound
method based on communication complexity for regular expression size
is developed to show that the required size is indeed nΘ(log n).
For constant alphabet size the best lower bound known to date is?(n2),
even when allowing in?nite languages and nondeterministic?nite au-
tomata.As the technique developed here works equally well for determin-
istic?nite automata over binary alphabets,the lower bound is improved
to n?(log n).
1Introduction
One of the most basic theorems in formal language theory is that every?nite au-tomaton can be converted into an equivalent regular expression,and vice versa, see e.g.[7].While algorithms accomplishing these tasks were known for a long time,there has been a renewed interest in these classical problems during the last few years.For instance,new algorithms for converting regular expressions into?-nite automata outperforming classical algorithms have been found only recently, as well as a matching lower bound of?(n·(log n)2)on the minimum number of transitions required by any equivalent nondeterministic?nite automaton(NFA). The lower bound is,however,only reachable for growing alphabets,and a better algorithm is known for constant alphabet size,see[20]and references therein.
In contrast,much less is known about the converse direction,namely of con-verting?nite automata into regular expressions.Apart from the fundamental nature of the problem,some applications of converting?nite automata into reg-ular expression lie in control?ow normalization,including uses in software engi-neering such as automatic translation of legacy code[17].All known algorithms covering the general case of in?nite languages are based on the classical ones compared in the survey[18].The drawback is that all of these(structurally sim-ilar)algorithms return expressions of size2O(n)in the worst case,and[3]exhibit a family of languages over a growing alphabet for which this exponential blow-up is inevitable.This leads to the quest for identifying structural restrictions on the
underlying transition graph of the given?nite automaton that can guarantee a shorter equivalent regular expression[4,16],as well as for heuristics improving the classical algorithms[6,2].
Another possibility is to concentrate on subfamilies of regular languages. For the important special case of unary languages,it has been established that every n-state nondeterminsitic?nite automaton can be converted in polynomial time into an equivalent regular expression of polynomial size[1,13,12].And for?nite languages,there exist equivalent regular expressions of size at most n O(log n)obtained by a classical construction,which is carefully analysed in[4]. In contrast,results from[3]show that size n?(log log n)can be necessary for?nite languages—at least for a growing alphabet.
Although there remains a considerable gap between the best known upper bounds and the lower bounds given some30years ago,to the best of our knowl-edge,only little progress has been made on this problem.The most preeminent gap between the upper and lower bounds presented in[3]is in the case of?nite languages.There the upper and lower bounds of n O(log n)and n?(log log n),re-spectively,are essentially the best ones known to date.We close this gap,giving that the blow-up for?nite languages is nΘ(log n)in the worst case,when switch-ing the representation from a?nite automaton to a regular expression.To this end,we develop a new lower bound technique for regular expression size based on communication complexity.Ellul et al.[4]prove a lower bound of?(n2)on the size of regular expressions for a?nite language over the binary alphabet by a reduction to Boolean circuit complexity.We improve this approach by utilizing a technique used to obtain better lower bounds for monotone Boolean circuits, using the communication complexity of search problems as introduced by Karch-mer and Wigderson[8].Our approach shows that the lower bound can even be realized for a n-state deterministic?nite automaton over a binary alphabet.
Recently,it was proposed that encoding the in?nite languages given in[3]over a4-letter alphabet in a straightforward manner will result in in?nite languages giving a lower bound of?(2n1/3)[21].However,this approach does not work,as we can give regular expressions of polynomial size for this family of languages. Thus the best lower bound known previously on the conversion problem for regular languages over alphabets of constant size is?(n2),established in[4]. Since?nite languages are regular,also this lower bound is lifted to n?(log n).
We also show that the family of?nite languages(over a growing alphabet) from[3]captures the combinatorial core of the conversion problem for?nite languages,as they form in some precise sense the hardest languages for this problem.We then use this to obtain a slight improvement of the best known upper bounds on this conversion problem.
2Preliminaries
2.1Formal Languages
We assume the reader to be familiar with the basic notions in formal language and automata theory as contained in[7].In particular,letΣbe an alphabet
andΣ?the set of all words over the alphabetΣ,including the empty wordλ. The length of a word w is denoted by|w|,where|λ|=0,and the total number of occurrences of the alphabet symbol a in w is denoted by|w|a.
In order to?x the notation,we brie?y recall the de?nition of regular expres-sions and the languages described by them:
De?nition1.LetΣbe an alphabet.The regular expressions overΣand the languages that they denote are de?ned recursively as follows:
–?is a regular expression and denotes the empty language;
–For a∈Σ∪{ε},a is a regular expression and denotes the language{a},
–if e and f are regular expressions denoting languages E and F,then(e+f), (e·f)and(e)?are regular expressions denoting the languages E∪F,E·F and E?,respectively.
Finally,the language described by the regular expression E is denoted by L(E).
For convenience,parentheses are sometimes omitted and the product is sim-ply written as juxtaposition.The priority of operators is speci?ed in the usual fashion:product is performed before disjunction,and star before both product and disjunction.We also write sometimes L1+L2to denote the union of the lan-guages L1and L2.The alphabetic width(or size)alph(E)of a regular expression E is de?ned as the total number of occurrences of symbols inΣin E.For a reg-ular language L we de?ne alph(L)as the minimum alphabetic width among all regular expressions describing L.As we will be primarily concerned with small regular expressions,we recall the notion of uncollapsible regular expressions[4]: De?nition2.Let E be a regular expression.We say that E is uncollapsible if all of the following conditions hold:
–If E contains the symbol?,then E=?.
–E contains no subexpression of the form F G or GF,with L(F)={ε}
–if E contains a subexpression of the form F+G or G+F with L(F)={ε}, thenε/∈L(G).
–if E contains a subexpression of the form F?,then L(F)={ε}.
The reader might have noticed that we have added a fourth condition not present in the original de?nition.This condition ensures that the star operator cannot occur in uncollapsible regular expressions describing?nite languages.
It is easily seen that for every collapsible regular expression,there is an uncollapsible one specifying the same language of at most the same size.
2.2Communication Complexity
Let X,Y,Z be?nite sets and R?X×Y×Z a ternary relation on them.In the search problem R,we have Alice given some input x∈X,Bob is given some input y∈Y.Initially,no party knows the other’s input,and Alice and Bob both want to output some z such that(x,y,z)∈R,by communicating as few bits
as possible.A communication protocol is a binary tree with each internal node v labeled either by a function a v:X→{0,1}if Alice transmits at this node, or b v:Y→{0,1}if Bob transmits at this node.Each leaf is labeled by an output z∈Z.We say that a protocol solves the search problem for relation R if for every input pair(x,y)∈X×Y,walking down the tree according to the functions a v and b v leads to a leaf labeled with some z satisfying(x,y,z)∈R. The protocol partition number C P(R)denotes the minimum number of leaves among all protocols solving the search problem for R.For a thorough treatment of communication complexity,the reader might want to consult[10].
3A new Lower Bound Technique for Regular Expression Size
In this section,we show how techniques from communication complexity can be used for proving lower bounds on the size of regular expression for homogeneous languages.
De?nition3.A regular expression E describing a homogeneous language is called a homogeneous expression,if none of the symbols?,εand?occur in E, or L(E)is empty and E=?.
Lemma4.For n≥1,let L?Σn be a homogeneous language.If E is an un-collapsible regular expression describing L,then E is a homogeneous expression. Proof.For the case L(E)=?,the statement immediately follows from the de?-nitions.Assume E is uncollapsible and??L(E)?Σn.We can rule out that any subexpression F with L(F)=?occurs in E:Every regular expression denoting the empty language contains the symbol?at least once.
Next,?niteness of the described languages is invariant under the operations +and·,but not by the Kleene star:For any regular expression F,the set denoted by F?is in?nite unless L(F)=?or{ε}.We have already ruled out the existence of?symbols in E.Since E is uncollapsible,it does not contain any subexpression of the form F?with L(F)={ε}either.Thus,the language L(E) being?nite,E cannot have any subexpression of the form F?.
Finally,we rule out the possibility thatεoccurs in E:As all words in L(E)are of length n,we make the following observation:If E contains a subexpression of the form F+G,then there exists m≤n such that both L(F)and L(G)contain only strings of length m.If alph(E)≤1,then clearly E has noε-subexpression. Assume alph(E)>1andεoccurs in E.Since E is uncollapsible,E contains a subexpression of the form F+εwithε/∈F and F=?.But then F+εdescribes a set of strings having di?erent lengths,a property which is inherited to E,as E has no subexpressions describing the empty language.??
Let(Σ,<)=(a1 ↑(L)={w∈Σn|u≤w for some u∈L}. A homogeneous language L?Σn is called monotonic,if L=↑(L). The next proposition shows that for homogeneous languages,the operator↑commutes with union and concatenation. Proposition5.For homogeneous languages L1and L2, ↑(L1)+↑(L2)=↑(L1+L2)and↑(L1)·↑(L2)=↑(L1·L2).??We establish next that homogeneous monotonic languages can be expressed by regular expressions in some normal form,and that the conversion into this normal form increases the expression size at most by a factor of|Σ|. A homogeneous expression is called a sum if it uses+as the only operator, i.e.it is of the form(b1+...+b m)for b i∈Σ.Let E be a homogeneous expression and F a subexpression of E.The subexpression F is called a maximal sum in F if E is a sum,but each subexpression G having F as a proper subexpression is not a sum.Note that the maximal sums in a homogeneous expression each describe a subset ofΣ.For a homogeneous expression E,the number of maximal sums in E is denoted by s(E).Since any non-redundant sum is of size at most|Σ|and contains at least one alphabetical symbol,we get s(L)≤alph(L)≤|Σ|·s(L)for every homogeneous language L. A homogeneous expression E is called monotonic if each maximal sum F in E describes a monotonic language,that is L(F)=↑(L(F)). Lemma6.For each homogeneous expression E over an ordered alphabetΣ, there exists a monotonic expression with L(F)=↑(L(E))and s(F)=s(E). Proof.The claim is shown by induction on s(E).In the base case s(E)=1,E is itself a sum.Let b be the minimal letter occurring in E,and let b1,...,b m be those letters inΣwith b i≥b.We set F:=(b1+...+b m),and we clearly have L(F)=↑(L(E))as well as s(F)=s(E)=1,hence the claim holds. Now let s(E)>1,and thus E=E1?E2where?is+or·,and in the latter case,E1and E2are not sums.Thus we have s(E)=s(E1)+s(E2)and hence s(E i) By the induction hypothesis,we get expressions F i with L(F i)=↑(L(E i)) and s(F i)=s(E i).We set F:=F1?F2,and we obtain s(F)=s(F1)+s(F2)= s(E1)+s(E2)=s(E).By Proposition5,we obtain L(F)=↑(L(E1))?↑(L(E2))=↑(L(E1)?L(E2))=↑(L(E)),so the claim holds.??For a homogeneous language??L?Σn,the search problem R L?L×(Σn\L)×[n]is de?ned by:(v,w,i)∈R L i?v i=w i.If L is monotonic,then additionally the monotonic search problem R m L is de?ned by(v,w,i)∈R m L i?v i>w i.These problems are similar to the search problems of[8]de?ned for (monotone)Boolean functions. Lemma7.For every homogeneous language L with??L?Σn and n≥1, s(L)≥C P(R L). Moreover,if L is monotonic,then s(L)≥C P(R m L). Proof.Let E be a regular expression with L(E)=L.By Lemma4,we can assume that E is homogeneous.If E is a homogeneous regular expression with L(E)homogeneous,then for every subexpression F of E the language L(F)is homogeneous as well,and we denote byλ(F)the length of the words in L(F). We will now,given a homogeneous regular expression E for L,construct a protocol for R L with s(E)many leaves. Recall that Alice is given an input x∈L,Bob a y/∈L,and they have to ?nd an index i with x i=y i.At each state of the protocol,Alice and Bob keep a subexpression F of E together with an interval[i,j]of length j?i+1=λ(F),satisfying the invariant that x i...x j∈L(F)and y i...y j/∈L(F).At the beginning F=E and[i,j]=[1,n],hence the invariant holds. At a state of the protocol with a subexpression F=F0+F1with s(F)>1 and interval[i,j],it must hold that either x i...x j∈L(F0)or x i...x j∈L(F1), but y i...y j/∈L(F0)and y i...y j/∈L(F1).Thus Alice can transmitδ=0,1such that x i...x j∈L(Fδ),and the protocol continues with F updated to Fδand [i,j]unchanged. At a state with subexpression F=F0·F1and interval[i,j],let?:=i+λ(F0)?1.Then it must hold that x i...x?∈L(F0)and x?+1...x j∈L(F1), but either y i...y?/∈L(F0)(case0)or y?+1...y j/∈L(F1)(case1).Then Bob can transmitδ=0,1such that caseδholds,and the protocol continues with F updated to Fδand[i,j]set to[i,?]in case0and[?+1,j]in case1. At a state with a subexpression F that is a maximal sum in E,it must be the case that i=j,and that x i∈L(F)and y i/∈L(F),hence in particular x i=y i and the protocol can terminate with output i. Obviously,the protocol solves R L,and the tree of the protocol constructed is isomorphic to the parse tree of E with its maximal sums at the leaves,thus the number of leaves is s(E). If L happens to be monotonic,then by Lemma6we can assume that E is a monotonic expression.Then also all subexpressions of E that appear in the above proof are monotonic,and in the terminating case it must moreover be the case that x i>y i,therefore the protocol solves R m L.?? 4Lower Bounds for the Conversion Problem For given integers?,n,we de?ne a family of graphs F?,n with parameters?,n as the set of directed graphs whose vertex set V is organized in?+2layers,with n vertices in each each layer.Hence we assume V={ i,j |1≤i≤n,0≤j≤?+1}.For all graphs in F?,n,we require in addition that each edge connects a vertex in some layer i to a vertex in the adjacent layer i+1. The following de?nition serves to represent the set F?,n as a?nite set of strings over the alphabet{0,1}:Fix a graph G∈F?,n for the moment.Let e(i,j,k)=1if G has an edge from vertex i in layer j to vertex k in layer j+1,and let e(i,j,k)=0otherwise.Next,for vertex i in layer j,the word f(i,j)=e(i,j,1)e(i,j,2)···e(i,j,n)encodes the set of outgoing edges for this vertex.Then for layer j,the word g(j)=f(1,j)f(2,j)···f(n,j)encodes the set of edges connecting vertices in layer j to vertices in layer j+1,for0≤j≤?. Finally,the graph G is encoded by the word w(G)=h(0)h(1)···h(?).It is easy to see that each word in the set{0,1}n2(?+1)can be uniquely decoded as a graph in the set F?,n. A graph G∈F?,n belongs to the subfamily fork?,n,if there exists a simple path starting in 1,0 ending eventually in a fork,i.e.,a vertex of outdegree at least two.The goal of this section will be to show that the language L=L?,n={w∈{0,1}n2(?+1)|w=w(G)with G∈fork?,n} can be accepted by a DFA of size polynomial in both parameters,while this cannot be the case for any regular expression describing this language. Proposition8.For every pair(?,n)with?≥2and n≥5,the language L?,n can be accepted by a DFA having at most?·n4states. Proof.We describe a DFA A accepting L,which has special states q j i for1≤ i≤n and0≤j≤?+1.These states will have the following property:If G has a simple non-forking path starting in vertex 1,0 and ending in vertex i,j ,then the DFA is in state q i,j after reading the?rst j·n2letters of the word w(G).A DFA having this property is obtained by setting q01to be the start state,and by applying the construction shown in in Figure4one by one to all states q j i,for 1≤i≤n and0≤j≤?. Each transition in Figure4labeled with some regular expression has to be unrolled to a simple path. To complete the construction,we have to ensure that from every state q for whichδ(q,1)is not yet de?ned,the transitionδ(q,1)leads to a state that leads every su?x of admissible length to an accepting state.This will be achieved by adding the transition structure of another deterministic?nite automaton that accepts{0,1}n2(?+1),and routing the lacking transitions into states of this automaton appropriately,in a way that each time the su?xes of admissible length are accepted. Next we count the number of states in A:Unrolling the construction depicted in Figure4introduces ? j=0n i=1 n·i+n k=1(n+1?k+n2?n·i) states,excluding the dead state.All dead states can be merged,and the minimal DFA accepting the language{0,1}n2(?+1)has n2(?+1)+2states,one of which is already a dead state.By adding up and simplifying,we see that the number of states equals (?+1)(1 2 n3+2n2)+2. We have?+1< √ 2 n4+1√ ... Fig.1.Connecting q j i to the corresponding states in the next layer. Proposition 9.Let L =L ?,n .Then s(L )=C P (R m L )≥2?(log n )/4?·?log ??≥44log ?=n (1/4?o (1))log ?. Proof.Let W :={1,...,n }?,and consider the relation FORK ?,n ?W ×W ×{0,...,?}de?ned as follows:given strings x and y in W ,set x 0=y 0=1,x ?+1=n ?1and y ?+1=n .Then (x,y,i )∈FORK ?,n i?x i =y i and x i +1=y i +1.The following lower bound on the protocol partition number of this relation was shown by Grigni and Sipser [5]: Lemma 10.C P (FORK ?,n )≥2?(log n )/4?·?log ?? ?? To complete the proof of Proposition 9,we show that for L =L ?,n ,any protocol for R m L can be used to solve FORK ?,n without any additional communication,which implies the stated lower bound.The reduction is similar to one used by Grigni and Sipser [5]. From her input x∈W,Alice computes a graph G x∈F?,n having for every 0≤i≤?an edge from x i,i to x i+1,i+1 ,and an additional edge from x?,? to n,?+1 .By construction,G x∈fork?,n and thus w(G x)∈L?,n. Similarly,from his input y∈W,Bob computes a graph G y having for every 0≤i≤?an edge from y i,i to y i+1,i+1 .Additionally,G y has all the edges from i,j to i′,j+1 where i=y j and i′is arbitrary.Therefore G y/∈fork?,n and thus w(G y)/∈L?,n. Now running the protocol for R m L on w(G x)and w(G y)yields a position k where w(G x)k=1and w(G y)k=0,i.e.,an edge that is present in G x,but not in G y.By construction,this edge goes from x i,i to x i+1,i+1 for some i,and it must be that y i=x i and y i+1=x i+1,as otherwise the edge would be present in G y.Thus i is a solution such that(x,y,i)∈FORK?,n.??Theorem11.There exist in?nitely many languages L m such that L m is ac-ceptable by a DFA with at most m states,but alph(L m)≥4m14. Proof.We have to adjust the parameter pair(?,n)for the language L?,n such that the gap between m=?·n4and n(1/4?o(1))log?is large. If we write?=nζ,then m=n4+ζ,and with both n=m14+ζ, the latter expression can be rewritten in terms of m andζas mζ 4(ζ+4)2 has a unique maximum atζ=4,and f(4)=1 n?·n 1 4m1 5.1A Poor Lower Bound For n even,consider the languages of palindromes of length n,L n={ww R| w∈{0,1}n/2}.These language can be described by n-ary Boolean functions f n(x1,x2,...,x n)as the set{x1·x2···x n|f n(x1,x2,...,x n)=1}.We call the n-ary function f the characteristic function of L n.This language is not monotonic,so only the lower bound based on the relation R L is applicable. To give an upper bound on C P(R L n ),we exploit the known fact that this number equals the minimum size among all Boolean formulas describing the characteristic function of L n[10]—here by the size of a formula,we mean the total number of occurrences of variables.The following formula of size2n describes the characteristic function: n/2 i=1(x i∧x n/2+i)∨(?x i∧?x n/2+i). For a lower bound on alph(L),we use the folklore fact that alph(L)is bounded below by the minimum number of states required by a nondeterministic?nite automaton accepting L.However,it is well known that every nondeterministic ?nite automaton accepting L n has size exponential in n[15]. 5.2Optimal Expressions for Parity Let par n denote the parity language{w∈{0,1}n;|w|1odd}.In[4],it is shown that alph(par n)=?(n2)using Khrapchenko’s bound[9]on the Boolean formula size of the parity function.From a recent improvement of this bound by Lee[11], we obtain the following better lower bound: Theorem12.If E is a regular expression with L(E)=par n,and n=2d+k with k<2d,then alph(E)≥2d(2d+3k). We will now construct regular expressions for par n that exactly match this lower bound.The construction is essentially the same as Lee’s[11]upper bound for the size of Boolean formulas for parity,but our analysis is simpler,using only induction and elementary arithmetic. We have that par n=L(odd n),where the expressions even n and odd n are de?ned inductively by even1:=0odd1:=1 even2m:=(even m·even m)+(odd m·odd m) odd2m:=(even m·odd m)+(odd m·even m) even2m+1:=(even m+1·even m)+(odd m?1·odd m) odd2m+1:=(even m+1·odd m)+(odd m+1·even m) First we observe that alph(even n)=alph(odd n)for every n,and we denote it by r(n):=alph(even n).Then the function r(n)satis?es the following recursive equations: r(1)=1r(2m)=4r(m)r(2m+1)=2r(m+1)+2r(m) We now show that if n=2d+k with k<2d,then r(n)=2d(2d+3k),by induction on n.Thus our expressions match Lees lower bound. The case n=1is obvious.For the induction step,we distinguish three cases. The?rst case is n=2m where m=2d+k,hence n=2d+1+2k.In this case we have r(n)=4r(m)=4·2d(2d+3k)=2d+1(2d+1+6k). The second case is n=2m+1where m=2d+k and m+1=2d+(k+1)with k+1<2d,hence n=2d+1+2k+1with2k+1<2d+1.In this case we obtain r(n)=2r(m+1)+2r(m)=2d+1(2d+3k+3)+2d+1(2d+3k) =2d+1(2d+1+6k+3). The?nal case is n=2m+1,where m=2d+k and m+1=2d+1,thus k=2d?1 and n=2d+1+(2d+1?1).In this case we calculate r(n)=2r(m+1)+2r(m)=22d+3+2d+1(2d+3(2d?1)) =2d+1(2d+2+2d+3(2d?1))=2d+1(2d+1+2d+1+2d+3(2d?1)) =2d+1(2d+1+3·2d+3(2d?1)=2d+1(2d+1+3(2d+1?1)) which shows the claim. 6Upper Bounds for Converting NF As into Regular Expressions In this section,we identify a family of?nite languages H n which are the hardest ?nite languages for the NFA to RE conversion,where by hardest,we mean that every n-state NFA over an alphabetΣcan be converted into a regular expression whose size is bounded above by|Σ|·alph(H n).Of course,we have to take the alphabet size into account:The setΣcan be accepted by a2-state NFA,while alph(Σ)is clearly equal to the size of the alphabet.The language used in the next theorem was studied already in[3],where it was shown that this language is hard for the conversion problem in some sense,that is the smallest regular expression for this language has size at least n?(log log n). Theorem13.For n≥1,let G n=(V n,?)be the complete directed acyclic graph on n vertices,that is V n={1,2,...,n}and edge set?={ i,j |1≤i< j≤n}.De?ne the language H n??≤n?1as the set of all paths in G leading from vertex1to vertex n.Then the following holds: 1.H n can be accepted by a n-state nondeterministic?nite automaton. 2.LetΣbe an alphabet.For every?nite language L overΣacceptable by a n-state nondeterministic?nite automaton holds alph(L)≤|Σ|·alph(H n). Proof.The?rst statement is easy to see.For the second statement,assume the theorem holds for all values up to n?1,and let A be a n-state nondeterministic ?nite automaton accepting L?Σ≤n?1.Without loss of generality,we assume A has state set{q1,q2,...,q n}and the states are in topological order with respect to the transition structure of the directed acyclic graph underlying A,that is, the automaton cannot move from state q j to state q i if i≤j.Furthermore,we can safely assume that the automaton has start state q1and single accepting state q n.This can be achieved by the following construction:If q1is not the start state,and the state set is topologically ordered,then q1is not reachable from the start state.q1can be removed,and we can apply the theorem for the obtained n?1-state automaton.For similar reasons,we can assume that q n is a ?nal state.If A has another?nal state p,we add transitions such that for every transition entering p there is now a transition from the same source entering q n. Then we remove p from the set of?nal states.Clearly,the accepted language is not altered by this construction,and the number of states remains n. Let H be the minimal partial n-state deterministic?nite automaton accept-ing H n,i.e.the automaton has no dead state.We again assume that the state set of H is topologically ordered,as for A. Let F and G be the regular expressions obtained by applying the standard state elimination algorithm[7,14]to the automata H and A,respectively.Since the algorithm is correct,we have L(F)=H n,and L(G)=L(A).For a pair of states(q i,q j)with i Now let F′be an expression of minimal alphabetic width describing H n,that is L(F′)=L(F).Then this equality is derivable using a sound and complete proof system for regular expression equations,e.g.see[19].Then we can derive the equality L(sub(F′))=L(sub(F))by a single application of the substitution rule[19],and recall sub(F)=G.To estimate the size of L(G),we simply observe that alph(F ij)≤|Σ|,for all i,j.??Thus an algorithm which does the job for the n-state automaton accepting H n will not perform much worse given any other?nite automaton of equal size. In doing this,we obtain a slightly improved upper bound for the conversion problem for all?nite languages—the currently best known method[4,Cor.22] gives a bound of(n+1)·kn(n?1)log n+1: Corollary14.Let A be a n-state nondeterministic?nite automaton accepting a?nite language L=L(A)over a k-symbol alphabet.Then alph(L) Proof.By the preceding theorem,it su?ces to give an upper bound on alph(H n). The language H n coincides with set of all walks(of length at most n?1)in G n that start in vertex1and end in vertex n.The analysis given in[4,Thm.20] implies that there exists a regular expression of size at most n(n?1)log(n?1)+1 describing this set,since for each pair(i,j),there is a regular expression of size at most1describing the set of walks of length at most1in G n starting in i and end in j.Thus,alph(H n)≤n(n?1)log(n?1)+1.??In[3],also a family of in?nite languages K n was considered.These languages are acceptable by n-state?nite automata,but all equivalent regular expressions require size2?(n).Formally,let G n=(V n,?)be the complete directed graph on n vertices,that is V n={1,2,...,n}and edge set?={ i,j |1≤i,j≤n}. De?ne the language K n???as the set of all walks in G n starting at vertex 1and ending at vertex n.Admittedly,these languages appear to be somewhat unnatural in that the alphabet size is growing rapidly with the number of states in the given?nite automaton.Recently it was suggested that using a binary encoding with start-and endmarkers of the abovementioned language K n would give a similar exponential blow-up[21];a proof sketch mimicking the techniques from[3]for large alphabets is included.The example from[21]is de?ned via the following encoding:For simplicity,assume n=2k for some k∈N.Then the |?|=n2alphabet symbols can be represented as binary strings in{0,1}2k.Fix such a binary encoding,denoted by f( i,j ).Then the map h:?→{a,b,0,1}, given by h( i,j )=a·f( i,j )·b naturally extends to a map h:??→{a,b,0,1}?by setting h(ε)=ε,and h(x·y)=h(x)·h(y),for all x,y∈??.It is argued then that the language h(L)as well requires regular expressions of size2?(n). Unfortunately,this argument is not complete:If we choose a binary encoding satisfying f( i,j )=g(i)·g(j),(1) where g is an arbitrary k-bit encoding of the integers1,...n,the following regular expression of size O(n log n)describes h(L): a·g(1)· (g(1)ba·g(1))?·(g(2)ba·g(2))?···(g(n)ba·g(n))? ?·g(n)b. Unfortunately,there seems not to be a straightforward way to make the argu-ment given in[21]complete.One might try and choose a more sophisticated encoding not satisfying Condition(1),which will make it harder to?nd a short corresponding equivalent regular expression.But this approach does not lend itself for a a possible proof technique for showing that?nding a short regular expression would be de facto impossible.So the best lower bound on the con-version problem for constant alphabet size remains the result from Theorem11, even if we allow in?nite languages. 7Conclusions and Further Work We developed a new lower bound technique for regular expression size to show that converting deterministic?nite automata accepting?nite languages into reg-ular expression leads to an inevitable blow-up in size of nΘ(log n),solving an open problem stated in[3].This bound still holds when restricting to alphabet size two.Note that?nite automata accepting unary?nite languages can be easily converted into regular expressions of linear size. Still,we feel that we have a limited understanding of the power of regular expressions in terms of descriptional complexity.The most notable open prob-lem is to determine better upper and lower bounds for the mentioned conversion problem for in?nite regular languages over alphabets of constant size,also stated in[4].Generalizations or improvements of the techniques developed in this paper might help to further raise,for the case of in?nite languages,the lower bound obtained here.Another line of research would be to try to apply the techniques developed here to improve the bounds obtained in[4]on the descriptional com-plexity of basic operations on regular expressions,like intersection,complement or language quotients.Here,many of the gaps between upper and lower bounds are exponential,which is in stark contrast to the many exact bounds known for such operations on?nite automata. Acknowledgement.We would like to thank Je?rey Shallit for kindly providing us a copy of the thesis[21]and the corrected?nal version[4],which will appear soon. References 1.M.Chrobak.Finite automata and unary languages.Theoretical Computer Science, 47(2):149–158,1986.Errata in302(1–3):497–498,2003. 2.M.Delgado and J.Morais.Approximation to the smallest regular expression for a given regular language.In M.Domaratzki,A.Okhotin,K.Salomaa,and S.Yu, editors,Conference on Implementation and Application of Automata,CIAA2004, volume3317of Lecture Notes in Computer Science,pages312–314,2004. 3. A.Ehrenfeucht and https://www.wendangku.net/doc/0d8925372.html,plexity measures for regular expressions. Journal of Computer and Systems Sciences,12(2):134–146,1976. 4.K.Ellul,B.Krawetz,J.Shallit,and M.Wang.Regular Expressions:New Re- sults and Open Problems.Journal of Automata,Languages and Combinatorics, 10(4):407–437,2005.to appear. 5.M.Grigni and M.Sipser.Monotone separation of logarithmic space from logarith- mic depth.Journal of Computer and System Sciences,50:433–437,1995. 6.Y.Han and D.Wood.Obtaining shorter regular expressions from?nite-state automata.Theoretical Computer Science,370(1-3):110–120,2007. 7.J.E.Hopcroft and J.D.Ullman.Introduction to Automata Theory,Languages and Computation.Addison-Wesley,1979. 8.M.Karchmer and A.Wigderson.Monotone circuits for connectivity require super- logarithmic depth.SIAM Journal on Computing,3:255–265,21990. 9.V.M.Khrapchenko.Methods for determining lower bounds for the complexity of π-schemes(English translation).Math.Notes Acad.Sciences USSR,10:474–479, 1972. 10. E.Kushilevitz and https://www.wendangku.net/doc/0d8925372.html,munication complexity.Cambridge University Press,New York,1997. 11.T.Lee.A new rank technique for formula size lower bounds.In W.Thomas and P.Weil,editors,Symposium on Theoretical Aspects of Computer Science,STACS 2007,volume4393of Lecture Notes in Computer Science,2007. 12. B.Litow.A special case of unary language containment.Theory of Computing Systems,39:743–751,2006. 13. A.Martinez.E?cient computation of regular expressions from unary NF As.In J.Dassow,M.Hoeberechts,H.J¨u rgensen,and D.Wotschke,editors,Workshop on Descriptional Complexity of Formal Systems2002,pages216–230,London, Canada,2002. 14.R.McNaughton and H.Yamada.Regular expressions and state graphs for au- tomata.IRA Transactions on Electronic Computers,9(1):39–47,1960. 15. A.R.Meyer and M.J.Fischer.Economy of description by automata,grammars, and formal systems.In IEEE Symposium on Switching and Automata Theory1971, pages188–191,1971. 16.J.J.Morais,N.Moreira,and R.Reis.Acyclic automata with easy-to-?nd short regular expressions.In J.Farr′e,I.Litovsky,and S.Schmitz,editors,Conference on Implementation and Application of Automata,CIAA2005,volume3845of Lecture Notes in Computer Science,pages349–350,2005. 17.P.H.Morris,R.A.Gray,and R.E.Filman.Goto removal based on regular expressions.Journal of Software Maintenance,9(1):47–66,1997. 18.J.Sakarovitch.The language,the expression,and the(small)automaton.In J.Farr′e,I.Litovsky,and S.Schmitz,editors,Conference on Implementation and Application of Automata,CIAA2005,volume3845of Lecture Notes in Computer Science,pages15–30,2005. 19. A.Salomaa.Two complete axiom systems for the algebra of regular events.Journal of the ACM,13(1):158–169,1966. 20.G.Schnitger.Regular expressions and nfas withoutε-transitions.In B.Durand and W.Thomas,editors,Symposium on Theoretical Aspects of Computer Science, STACS2006,volume3884of Lecture Notes in Computer Science,pages432–443, 2006. 21.V.Waizenegger.¨Uber die E?zienz der Darstellung durch regul¨a re Ausdr¨u cke und endliche Automaten.Diplomarbeit,Rheinisch-Westf¨a lische Technische Hochschule Aachen,Fachbereich Informatik,2000. 实验一、复变函数与特殊函数图形的绘制 一、复变函数图形的绘制 例题：编程绘制出复变函数31/31 ，的图形。 z z , z 解： %experiment1.m close all clear all m=30; r=(0:m)'/m; theta=pi*(-m:m)/m; z=r*exp(i*theta); w=z.^3; blue=0.2; x=real(z); y=imag(z); u=real(w); v=imag(w); v=v/max(max(abs(v))); %%函数值虚部归一化 M=max(max(u)); m=min(min(u)); axis([-1 1 -1 1 m M]) caxis([-1 1]) %%指定颜色值的范围 s=ones(size(z)); subplot(131) mesh(x,y,m*s,blue*s) %%画投影图 hold on surf(x,y,u,v) %%画表面图 xlabel('x') ylabel('y') zlabel('u') title('z^3') hold off colormap(hsv(64)) %%画色轴 w=z.^(1/3); x=real(z); y=imag(z); subplot(132) for k=0:2 rho=abs(w); phi=angle(w)+k*2*pi/3; u=rho.*cos(phi); v=rho.*sin(phi); v=v/max(max(abs(v))); %%函数值虚部归一化 M=max(max(max(M,u))); m=min(min(min(m,u))); surf(x,y,u,v) %%画表面图 axis([-1 1 -1 1 m M]) hold on end s=ones(size(z)); mesh(x,y,m*s,blue*s) %%画投影图 xlabel('x') ylabel('y') zlabel('u') title('z^{1/3}') colormap(hsv(64)) %%画色轴 w=1./z; w(z==0)=NaN; x=real(z); y=imag(z); u=real(w); v=imag(w); v=v/max(max(abs(v))); %%函数值虚部归一化 M=max(max(max(M,u))); m=min(min(min(m,u))); subplot(133) surf(x,y,u,v) %%画表面图 hold on axis([-1 1 -1 1 m M]) s=ones(size(z)); mesh(x,y,m*s,blue*s) %%画投影图 xlabel('x') ylabel('y') zlabel('u') title('1/z') colormap(hsv(64)) %%画色轴 二次函数与特殊图形的存在性问题 类型一二次函数与等腰三角形 利用抛物线探求等腰三角形分三步:先分类，按腰相等分为三种情况;再根据两点间的距离公式列方程，后解方程并检验。 1．如图①，在平面直角坐标系xOy中，已知A（﹣2，2），B（﹣2，0），C（0，2），D（2，0）四点，动点M以每秒个单位长度的速度沿B→C→D运动（M不与点B、点D重合），设运动时间为t（秒）．（1）求经过A、C、D三点的抛物线的解析式； （2）点P在（1）中的抛物线上，当M为BC的中点时，若△PAM≌△PBM，求点P的坐标； （3）当M在CD上运动时，如图②．过点M作MF⊥x轴，垂足为F，ME⊥AB，垂足为E．设矩形MEBF与△BCD重叠部分的面积为S，求S与t的函数关系式，并求出S的最大值； （4）点Q为x轴上一点，直线AQ与直线BC交于点H，与y轴交于点K．是否存在点Q，使得△HOK 为等腰三角形？若存在，直接写出符合条件的所有Q点的坐标；若不存在，请说明理由． 类型二二次函数与直角三角形 利用抛物线探求直角三角形，逐次选择顶角进行讨论，一般运用勾股定理建立方程，然后解方程并检验。2．如果抛物线C1的顶点在拋物线C2上，抛物线C2的顶点也在拋物线C1上时，那么我们称抛物线C1与C2“互为关联”的抛物线．如图1，已知抛物线C1：y1＝x2+x与C2：y2＝ax2+x+c是“互为关联”的拋物线，点A，B分别是抛物线C1，C2的顶点，抛物线C2经过点D（6，﹣1）． （1）直接写出A，B的坐标和抛物线C2的解析式； （2）抛物线C2上是否存在点E，使得△ABE是直角三角形？如果存在，请求出点E的坐标；如果不存在，请说明理由； （3）如图2，点F（﹣6，3）在抛物线C1上，点M，N分别是抛物线C1，C2上的动点，且点M，N 的横坐标相同，记△AFM面积为S1（当点M与点A，F重合时S1＝0），△ABN的面积为S2（当点N与点A，B重合时，S2＝0），令S＝S1+S2，观察图象，当y1≤y2时，写出x的取值范围，并求出在此范围内S的最大值． （3）求出 m ＝﹣k 2﹣k √k 2 + 1，在△AHM 中，tan α= AH = ?k =k +√k 2 + 1 =tan ∠BEC = EK =k +2，即 2020 年中考数学大题狂练之压轴大题突破培优练（江苏专用） 专题 4 二次函数与特殊图形的存在性问题 【真题再现】 1．（2019 年盐城 27 题）如图所示，二次函数 y ＝k （x ﹣1）2+2 的图象与一次函数 y ＝kx ﹣k +2 的图象 交于 A 、B 两点，点 B 在点 A 的右侧，直线 AB 分别与 x 、y 轴交于 C 、D 两点，其中 k ＜0． （1）求 A 、B 两点的横坐标； （△2）若 OAB 是以 OA 为腰的等腰三角形，求 k 的值； （3）二次函数图象的对称轴与 x 轴交于点 E ，是否存在实数 k ，使得∠ODC ＝2∠BEC ，若存在，求出 k 的值；若不存在，说明理由． 【分析】（1）将二次函数与一次函数联立得：k （x ﹣1）2+2＝kx ﹣k +2，即可求解； （2）分 OA ＝AB 、OA ＝OB 两种情况，求解即可； HM m BK 在△AHM中，tanα= AH = ?k =k+√k2+1=tan∠BEC= EK =k+2， 可求解． 【解析】（1）将二次函数与一次函数联立得：k（x﹣1）2+2＝kx﹣k+2， 解得：x＝1和2， 故点A、B的坐标横坐标分别为1和2； （2）OA=√22+1=√5， ①当OA＝AB时， 即：1+k2＝5，解得：k＝±2（舍去2）； ②当OA＝OB时， 4+（k+2）2＝5，解得：k＝﹣1或﹣3； 故k的值为：﹣1或﹣2或﹣3； （3）存在，理由： ①当点B在x轴上方时， 过点B作BH⊥AE于点△H，将AHB的图形放大见右侧图形， 过点A作∠HAB的角平分线交BH于点M，过点M作MN⊥AB于点N，过点B作BK⊥x轴于点K， 图中：点A（1，2）、点B（2，k+2），则AH＝﹣k，HB＝1， 设：HM＝m＝MN，则BM＝1﹣m， 则AN＝AH＝﹣k，AB=√k2+1，NB＝AB﹣AN， 由勾股定理得：MB2＝NB2+MN2， 即：（1﹣m）2＝m2+（√k2+1+k）2， 解得：m＝﹣k2﹣k√k2+1， HM m BK 解得：k=±√3， 此时k+2＞0，则﹣2＜k＜0，故：舍去正值， 其中， 。 ! 4!3!21)(; ! 3!21)(; ! 21)(; 1)(;)exp(4 32443 23322211x x x x x P y x x x x P y x x x P y x x P y e x y x ++++==+++==++==+==== -3 -2-1 0123 -50 5 10 15 20 25 Figure 1 y=exp(x) and its Taylor expansion equation X Y 其中， 。 ! 7!5!3)(; !5!3)(; ! 3)(; )();sin(7 53775 35533311x x x x x P y x x x x P y x x x P y x x P y x y -+-==+-==-===== -4 -3-2-1 01234 -8-6-4-202468Figure 2 y=sin(x) and its Taylor expansion equation X Y 其中， 。 ! 8!6!4!21)(; !6!4!21)(; ! 4!21)(; !21)(); cos(8 642886 42664 2442 22x x x x x P y x x x x P y x x x P y x x P y x y +-+-==-+-==+-==-=== -4 -3-2-1 01234 -8-6 -4 -2 2 4 Figure 3 y=cos(x) and its Taylor expansion equation X Y 其中， 。 4 32)(; 3 2)(; 2 )(; )();1ln(4 32443 23322211x x x x x P y x x x x P y x x x P y x x P y x y -+-==+-==-====+= -1 -0.50 0.51 1.52 -3-2 -1 1 2 3 Figure 4 y=ln(x) and its Taylor expansion equation X Y 1.如图，已知抛物线2 1y x =-与x 轴交于A 、B 两点，与y 轴交于点C ． （1）求A 、B 、C 三点的坐标; （2）过点A 作AP ∥CB 交抛物线于点P ，求四边形ACBP 的面积; （3）在x 轴上方的抛物线上是否存在一点M ，过M 作MG ⊥x 轴于点G ，使以A 、M 、G 三点为顶点的三角形与?PCA 相似．若存在，请求出M 点的坐标；否则，请说明理由． 解：（1）令0y =，得2 10x -= 解得1x =± 令0x =，得1y =- ∴ A (1,0)- B (1,0) C (0,1)- ……………………3分 （2）∵O A =O B =O C =1 ∴∠BAC =∠AC O=∠BC O= 45 ∵A P ∥CB ， ∴∠P AB = 45 过点P 作P E ⊥x 轴于E ，则?A P E 为等腰直角三角形 令O E =a ，则P E =1a + ∴P (,1)a a + ∵点P 在抛物线21y x =-上 ∴2 11a a +=- 解得12a =，21a =-（不合题意，舍去） ∴P E =3……………………………………………………………………………5分 ∴四边形ACB P 的面积S =12AB ?O C +12AB ?P E =11 2123422 ??+??=………………………………6分 (3)． 假设存在 ∵∠P AB =∠BAC =45 ∴P A ⊥AC ∵MG ⊥x 轴于点G ， ∴∠MG A =∠P AC =90 在Rt △A O C 中，O A =O C =1 ∴AC =2 在Rt △P AE 中，AE =P E =3 ∴A P= 32 ………8分 设M 点的横坐标为m ，则M 2 (,1)m m - ①点M 在y 轴左侧时，则1m <- (ⅰ) 当?A MG ∽?P CA 时，有 AG PA =MG CA ∵A G=1m --，MG=2 1m -即2322 = 解得11m =-（舍去） 23m =（舍去）………9分 G M C B y P A o x 二次函数中特殊图形的存在性 教学目标1．学会二次函数中特殊图形的存在性问题的分析方法2．掌握三角形与四边形的存在性问题的解法 重、难点三角形与四边形的存在性问题的解法 知识梳理 1．两点之间的距离公式 如图所示，点A(x1,y1)，B(x2,y2)在平面直角坐标系中，那么AB＝． 2．中点坐标公式 如图，点A（x1，y1），B（x2，y2），点C为线段AB的中点，则点C的坐标为（，）． 3．“两线一圆”模型 如图，线段AB，在平面内找一点C使得△ABC为直角三角形．这样的点C的集合如下图所示（分别过点A，B作线段AB的垂线，并以AB为直径画圆，除点A，B以外的点都可以与点A，B构成直角三角形，这个模型简称“两线一圆”）． 4．平行四边行顶点坐标关系 如图，四边形ABCD为平行四边形，顶点坐标分别为A（x1，y1），B（x2，y2），C（x3，y3），D（x4，y4）． ①因为平行四边行的对角线互相平分，所以点O为AC和BD的中点，根据中点坐标公式可以得出：＝，＝，即x1＋x3＝x2＋x4，y1＋y3＝y2＋y4； ②因为BC可以看做AD平移得到的，所以点A的对应点为点B，点D的对应点为点C，根据平移的坐标关系可以得出：x2－x1＝ x3－x4，y2－y1＝y3－y4． 一、直角三角形的存在问题 知识点讲解1：直角三角形的存在问题 例 1. 如图，已知直线y＝x＋3与x轴交于点A，与y轴交于点B，抛物线y＝﹣x2＋bx＋c经过A、B两点，与x轴交于另一个点C，对称轴与直线AB交于点E，抛物线顶点为D． （1）求抛物线的解析式； （2）在第三象限内，F为抛物线上一点，以A、E、F为顶点的三角形面积为3，求点F的坐标； （3）点P从点D出发，沿对称轴向下以每秒1个单位长度的速度匀速运动，设运动的时间为t秒，当t为何值时，以P、B、C 为顶点的三角形是直角三角形？直接写出所有符合条件的t值． 实验1 曲线绘图 实验目的 ?学习Matlab绘图命令；?进一步理解函数概念。 1.曲线图 Matlab作图是通过描点、连线来实现的，故在画一个曲线图形之前，必须先取得该图形上的一系列的点的坐标（即横坐标和纵坐标），然后将该点集的坐标传给Matlab函数画图. 命令为： PLOT(X,Y,’S’) 线型 X,Y是向量,分别表示点集的横坐标和纵坐标 PLOT(X,Y)--画实线 PLOT(X,Y1,’S1’,X,Y2,’S2’,……,X,Yn,’Sn’) --将多条线画在一起 例1在[0,2*pi]用红线画sin(x),用绿圈画cos(x). x=linspace(0,2*pi,30); 解： y=sin(x); z=cos(x); plot(x,y,'r',x,z,‘g o') G 绿色o 圈 表1 基本线型和颜色 符号颜色符号线型y黄色.点 m紫红0圆圈c青色x x标记r红色+加号g绿色*星号b兰色-实线w白色:点线k黑色-.点划线 --虚线 2.符号函数(显函数、隐函数和参数方程)画图(1) ezplot ezplot(‘f(x)’,[a,b]) 表示在a 二次函数背景下的特殊图形问题 1.如图1，抛物线213442 y x x = --与x 轴交于A 、B 两点（点B 在点A 的右侧），与y 轴交于点C ，连结BC ，以BC 为一边，点O 为对称中心作菱形BDEC ，点P 是x 轴上的一个动点，设点P 的坐标为(m , 0)，过点P 作x 轴的垂线l 交抛物线于点Q ． （1）求点A 、B 、C 的坐标； （2）当点P 在线段OB 上运动时，直线l 分别交BD 、BC 于点M 、N ．试探究m 为何值时，四边形CQMD 是平行四边形，此时，请判断四边形CQBM 的形状，并说明理由； （3）当点P 在线段EB 上运动时，是否存在点Q ，使△BDQ 为直角三角形，若存在，请直接写出点Q 的坐标；若不存在，请说明理由． 2.如图1，抛物线233384 y x x =--+与x 轴交于A 、B 两点（点A 在点B 的左侧），与y 轴交于点C ． （1）求点A 、B 的坐标； （2）设D 为已知抛物线的对称轴上的任意一点，当△ACD 的面积等于△ACB 的面积时，求点D 的坐标； （3）若直线l 过点E (4, 0)，M 为直线l 上的动点，当以A 、B 、M 为顶点所作的直角三角形有且只有．．．．三个时，求直线l 的解析式． 作业、在直角坐标平面内，为原点，二次函数的图像经过A （-1，0） 和点B （0，3），顶点为P 。 （1）求二次函数的解析式及点P 的坐标； （2）如果点Q 是x 轴上一点，以点A 、P 、Q 为顶点的三角形是直角三角形，求点Q 的坐标。 O 2y x bx c =-++ 1.已知平面直角坐标系xOy中，抛物线y＝ax2－(a＋1)x与直线y＝kx的一个公共点为A(4，8)． （1）求此抛物线和直线的解析式； （2）若点P在线段OA上，过点P作y轴的平行线交（1）中抛物线于点Q，求线段PQ长度的最大值； （3）记（1）中抛物线的顶点为M，点N在此抛物线上，若四边形AOMN恰好是梯形，求点N的坐标及梯形AOMN的面积． 备用图 1、函数fmincon()的具体格式为： X=fmincon(fun,x0,A,b) X=fmincon(fun,x0,A,b,Aeq,Beq,Lb,Ub) X=fmincon(fun,x0,A,b,Aeq,Beq,Lb,Ub,nonlcon,options) *X,fval,exitflag,output+=fmincon(fun,x0,…) [X,fval,exitflag,output,lambda,grad,Hessian+=fmincon(fun,x0,…) 参数中fun为目标函数，x0为变量的初始值，x为返回的满足要求的变量的值。A和b表示线性不等式约束，Aeq，Beq表示线性等式约束，Lb和Ub分别为变量的下界和上界约束，nonlcon表示非线性约束条件，options为控制优化过程的优化参数向量。返回值fval为目标函数。exitflag>0表示优化结果收敛于解，exitflag=0表示优化超过了函数值的计算次数，exitflag<0表示优化不收敛。lambda是拉格朗日乘子，显示那个约束条件有效。grad表示梯度，hessian表示汉森矩阵。例：使得目标函数在约束条件，下取得最小值。设计的程序如下：先把目标函数和约束条件分别编写成独立的m文件，注意，这样的m文件必须用function开头，并且文件名一定要和函数名一致。 目标函数的文件为：function f=objfun(x) f=exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1); 约束条件的文件为：function [c,ceq]=confun(x) c=[1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10]; %表示不等式非线性约束ceq=[]; %表示等式非线性约束 优化的程序如下： clear x0=[-1 1]; options=optimset('largescale','off','display','iter'); [x,fval,exitflag,output]=fmincon(@objfun,x0,[],[],[],[],[],[],@confun,options) 本文由nianhua0907贡献 优化工具箱提供fmincon函数用于对有约束优化问题进行求解，其语法格式如下： x = fmincon(fun,x0,A,b) x = fmincon(fun,x0,A,b,Aeq,beq) x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub) x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon) x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options) x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options,P1,P2, ...) [x,fval] = fmincon(...) [x,fval,exitflag] = fmincon(...) [x,fval,exitflag,output] = fmincon(...) 其中，x, b, beq, lb,和ub为线性不等式约束的上、下界向量，A 和Aeq “二次函数”常考题型总结 “二次函数”综合题往往考察以下几类，面积，周长、最值，或者与四边形、圆等结合考察一些相关的性质等，题目编号灵活，难度有点大，今天整理了常考题型，希望对同学们能有所帮助！ 面积类 1、如图,已知抛物线经过点A（-1,0）、B（3,0）、C（0,3）三点． 2、（1）求抛物线的解析式． 3、（2）点M是线段BC上的点（不与B,C重合）,过M作MN∥y轴交抛物线于N,若点M的横坐标为m,请用m的代 数式表示MN的长． 4、（3）在（2）的条件下,连接NB、NC,是否存在m,使△BNC的面积最大若存在,求m的值；若不存在,说明理由． 《 } 5、如图，抛物线y=ax2- 3/2 x-2(a≠0)的图象与x轴交于A、B两点，与y轴交于C点，已知B点坐标为（4，0）． 6、（1）求抛物线的解析式； 7、（2）试探究△ABC的外接圆的圆心位置，并求出圆心坐标； 8、（3）若点M是线段BC下方的抛物线上一点，求△MBC的面积的最大值，并求出此时M点的坐标． ? — 平行四边形类 3、如图，在平面直角坐标系中，抛物线y=x 2 +mx+n经过点A（3，0）、B（0，-3），点P是直线AB上的动点，过点P 作x轴的垂线交抛物线于点M，设点P的横坐标为t。 （1）分别求出直线AB和这条抛物线的解析式； （2）若点P在第四象限，连接AM、BM，当线段PM最长时，求△ABM的面积； （3）是否存在这样的点P，使得以点P、M、B、O为顶点的四边形为平行四边形若存在，请直接写出点P的横坐标；若不存在，请说明理由。 " 如图，在平面直角坐标系中放置一直角三角板，其顶点为A（0，1），B（2，0），O（0，0），将此三角板绕原点O逆时针旋转90°，得到△A'B'O． （1）一抛物线经过点A'、B'、B，求该抛物线的解析式； （2）设点P是在第一象限内抛物线上的一动点，是否存在点P，使四边形PB'A'B的面积是△A'B'O面积4倍若存在，请求出P的坐标；若不存在，请说明理由． （3）在（2）的条件下，试指出四边形PB'A'B是哪种形状的四边形并写出四边形PB'A'B的两条性质． 【 ^ 5、如图，抛物线y=x2-2x+c的顶点A在直线l：y=x-5上。 （1）求抛物线顶点A的坐标； （2）设抛物线与y轴交于点B，与x轴交于点C、D（C点在D点的左侧），试判断△ 二次函数与几何图形综合题 类型 1 二次函数与相似三角形的存在性问题 1．(2015·昆明西山区一模)如图，已知抛物线y＝ax2＋bx＋c(a≠0)经过A(－1，0)，B(4，0)，C(0，2) 三点． (1)求这条抛物线的解析式； (2)P 为线段BC 上的一个动点，过P 作PE 垂直于x 轴与抛物线交于点E，设P 点横坐标为m，PE 长度为y，请写出y 与m 的函数关系式，并求出PE 的最大值； (3)D 为抛物线上一动点，是否存在点D 使以A、B、D 为顶点的三角形与△COB 相似？若存在，试求出点D 的坐标；若不存在，请说明理由． 2．(2013·曲靖)如图，在平面直角坐标系xOy 中，直线y＝x＋4 与坐标轴分别交于A，B 两点，过A，B 两点的抛物线为y＝－x2＋bx＋c.点D 为线段AB 上一动点，过点D 作CD⊥x 轴于点C，交抛物线于点E. (1)求抛物线的解析式； (2)当DE＝4 时，求四边形CAEB 的面积； (3)连接BE，是否存在点D，使得△DBE 和△DAC 相似？若存在，求出D 点坐标；若不存在，说明理由． 3．(2015·襄阳)边长为 2 的正方形OABC 在平面直角坐标系中的位置如图所示，点D 是边OA 的中点，连接CD，点E 在第一象限，且DE⊥DC，DE＝DC.以直线AB 为对称轴的抛物线过C，E 两点． (1)求抛物线的解析式； (2)点P 从点C 出发，沿射线CB 以每秒 1 个单位长度的速度运动，运动时间为t 秒．过点P 作PF⊥CD 于点F.当t 为何值时，以点P，F，D 为顶点的三角形与△COD 相似？ (3)点M 为直线AB 上一动点，点N 为抛物线上一动点，是否存在点M，N，使得以点M，N，D，E 为顶点的四边形是平行四边形？若存在，请直接写出满足条件的点的坐标；若不存在，请说明理由． 类型 2 二次函数与平行四边形的存在性问题 1．(2014·曲靖)如图，抛物线y＝ax2＋bx＋c 与坐标轴分别交于A(－3，0)，B(1，0)，C(0，3)三点，D 几种特殊函数的图象及性质 备课教师：刘彩伏 教学目标：1、理解正比例函数、反比例函数、一次函数、二次函数的概念，掌握用“待 定系数法”求这些函数的解析式的方法，能用描点法画出上述函数的图象并观 察出它们的性质。 2、能够根据二次函数解析式确定图象的顶点坐标、对称轴方程及与x 轴、y 轴 的交点，初步了解数形结合的观点，并初步学会用这些观点去分析问题的方 法。 教学重点：各种函数的概念及图象性质；“待定系数法”求函数的解析式。 教学难点：“待定系数法”求函数的解析式，用数形结合的观点分析问题的方法。 计划课时：4课时（第一课时结合图形复习各种函数概念和性质，其余三课时为题型分析 与训练） 教学过程： 一、基础知识复习 1、正比例函数 [定义]：函数y=kx(k 是常数，k ≠0)。 [图象]：经过（0，0），（1，k ）两点的直线。 [性质]：k>0时，图象在一、三象限内，y 随x 的增大而增大；k<0时，图象在 二、四象限内，y 随x 的增大而减小。 2、反比例函数 [定义]：函数x k y =(k 是常数，k ≠0)。 [图象]：双曲线。 [性质]：k>0时，图象的两个分支在一、三象限内，在每一象限内，y 随x 的增大而减小；k<0时，图象的两个分支在二、四象限内，在每一象限内，y 随x 的增大而增大；两分支都无限接近但永远不能达到两坐标轴。 3、一次函数 [定义]：函数y=kx+b(k ，b 是常数，k ≠0)。（注意：当b=0时，就成为正比例函 数） [图象]：经过（0，b ），（k b -，0）两点的直线，与直线y=kx 平行。（k 叫做直线的斜率，b 叫做直线在y 轴上的截距） [性质]： y A x B O C D 专题：二次函数与几何图形 一、二次函数与平行四边形 1．已知抛物线c bx ax y ++=2 )0(≠a 过点A （-3，0），B （1,0），C （0,3）三点 (1)求抛物线的解析式； (2) 若抛物线的顶点为P ，求∠PAC 正切值； (3)若以A 、P 、C 、M 为顶点的四边形是平行四边形， 求点M 的坐标. 2．已知一次函数1y x =+的图像和二次函数2 y x bx c =++的图像 都经过A 、B 两点，且点A 在y 轴上，B 点的纵坐标为5. （1）求这个二次函数的解析式； （2）将此二次函数图像的顶点记作点P ，求△ABP 的面积； （3）已知点C 、D 在射线AB 上，且D 点的横坐标比C 点 的横坐标大2，点E 、F 在这个二次函数图像上，且CE 、 DF 与y 轴平行，当CF ∥ED 时，求C 点坐标. 二、二次函数与相似三角形 3.如图，直线y ＝x ＋3与x 轴、y 轴分别交于点A 、C ，经过A 、C 两点的抛物线y ＝ax 2 ＋bx ＋c 与x 轴的负半轴上另一交点为B ，且tan ∠CBO=3． （1）求该抛物线的解析式及抛物线的顶点D 的坐标； （2）若点P 是射线BD 上一点，且以点P 、A 、B 为顶点的 三角形与△ABC 相似，求P 点坐标．【2014徐汇区】 1 2345 -1 -1-2 123456 x y O 图8 x y O O N C M B A 4.已知：在直角坐标系中，直线y=x+1与x 轴交与点A ，与y 轴交与点B ，抛物线 21 ()2 y x m n =-+的顶点D 在直线AB 上，与y 轴的交点为C 。 （1）若点C （非顶点）与点B 重合，求抛物线的表达式；（2015杨浦区） （2）若抛物线的对称轴在y 轴的右侧，且CD ⊥AB ，求∠CAD 的正切值； （3）在第（2）的条件下，在∠ACD 的内部作射线CP 交抛物线的对称 轴于点P ，使得∠DCP=∠CAD ，求点P 的坐标。 三、二次函数与特殊三角形（Rt △ 等腰△ 等腰Rt △） 5．如图，已知二次函数y=-x 2 +bx+c （c>0）的图像与x 轴交于A 、B 两点（A 在B 左侧），与y 轴交于点C ，且OB=OC=3，顶点为M 。 （1）求二次函数的解析式。 （2）线段BM 上是否存在点N ，使得△NMC 为等腰三角形？ 若存在，求出点N 的坐标，若不存在，请说理。 6.已知二次函数y=ax 2 +bx+c (a ≠0)的图像经过点 (1)求此函数的解析式和对称轴. (2)试探索该抛物线在x 轴下方的对称轴上存在几个点P, 使△PAB 是直角三角形,并求出这些点的坐标. 说明： 1.试题左侧二维码为该题目对应解析； 2.请同学们在独立解答无法完成题目后再扫描二维码查看解析，杜绝抄袭； 3.查看解析还是无法掌握题目的，可按下方“向老师求助”按钮； 4.组卷老师可在试卷下载页面查看学生扫描二维码查看解析情况统计，了解班级整体 学习情况，确定讲解重点； 5.公测期间二维码查看解析免扣优点，对试卷的使用方面的意见和建议，欢迎通过“意 见反馈”告之。 2015年03月03日光辉职业的初中数学组卷 一．解答题（共30小题） 1．（2015?崇明县一模）如图，已知抛物线y=x2+bx+c经过直线y=﹣+1与坐标轴的两个交点A、B，点C为抛物线上的一点，且∠ABC=90°． （1）求抛物线的解析式； （2）求点C坐标； （3）直线y=﹣x+1上是否存在点P，使得△BCP与△OAB相似？若存在，请直接写出P点的坐标；若不存在，请说明理由． 2．（2015?三亚三模）如图，直线y=﹣x+2与x轴交于点B，与y轴交于点C，已知二次函数的图象经过点B、C和点A（﹣1，0）． （1）求B、C两点坐标； （2）求该二次函数的关系式； （3）若抛物线的对称轴与x轴的交点为点D，则在抛物线的对称轴上是否存在点P，使△PCD是以CD为腰的等腰三角形？如果存在，直接写出P点的坐标； 如果不存在，请说明理由； （4）点E是线段BC上的一个动点，过点E作x轴的垂线与抛物线相交于点F，当点E运动到什么位置时，四边形CDBF的面积最大？求出四边形CDBF的最大面积及此时E点的坐标． 3．（2015?金山区一模）如图，已知直线y=2x+6与x轴、y轴分别交于A、D两点，抛物线y=ax2+bx+2（a≠0）经过点A和点B（1，0）． （1）求抛物线的解析式； （2）在线段AD上取一点F（点F不与点A重合）．过点F作x轴的垂线交抛物线于点G、交x轴于点H．当FG=GH时，求点H的坐标； （3）设抛物线的对称轴与直线AD交于点E，抛物线与y轴的交点为C，点M 在线段AB上，当△AEM与△BCM相似时，求点M的坐标． 4．（2015?普陀区一模）如图，在平面直角坐标系xOy中，点A（m，0）和点B （0，2m）（m＞0），点C在x轴上（不与点A重合） （1）当△BOC与△AOB相似时，请直接写出点C的坐标（用m表示）（2）当△BOC与△AOB全等时，二次函数y=﹣x2+bx+c的图象经过A、B、C 三点，求m的值，并求点C的坐标 （3）P是（2）的二次函数图象上的一点，∠APC=90°，求点P的坐标及∠ACP 的度数． 一师一优课教学设计 【教学目标】 1．知识与能力：一要熟练掌握二次函数和平面几何的基础知识；二要利用几何图形和二次函数的有关性质和知识，充分挖掘题目中的隐含条件，达到解题的目的。 2．过程与方法：一要通过综合题的训练要求学生熟练掌握待定系数法、分类讨论、数形结合的数学思想方法；二要经历探究利用函数的模型表示线段长或面积的过程。 3．情感态度与价值观：一要通过探究，互相讨论，发表意见等学习过程，培养合作精神和认真倾听的习惯，二要经历探究面积的最值问题体会二次函数的应用价值和二次函数模型对解决最值问题的优越性。 【学情分析】二次函数综合题知识点多，覆盖面广，条件隐蔽，关系复杂，思路难觅，解法灵活，因此在解决此类综合题时，要求学生，一要树立必胜的信心，二要具备扎实的基础知识和熟练的解题技能，三要掌握常用的解题策略。 【教学重点难点】二次函数与几何图形相结合的综合问题 【教学过程】 一：探究问题，交流讨论 1：问题一：如图，在平面直角坐标系中，抛 物线经过A(-1,0),B(3,0),C(0,-1)三点。 （1）求该抛物线的表达式; （2）点Q在y轴上，点P在抛物线上， 要使以点Q、P、A、B为顶点的四边形是平行 四边形，求所有满足条件的点P的坐标。 2：合作交流; 分类讨论; 情况一、二 情况三 二：师生互动：（1）设该抛物线的表达式为y=ax 2+bx+c 根据题意，得 a- b+c=0 a=1 3 9a+3b+c=0 解之，得 b=2 3 - c=-1 c=-1 ∴所求抛物线的表达式为y=13x 2-2 3 -x-1 （2）①AB 为边时，只要PQ ∥AB 且PQ=AB=4即可。 又知点Q 在y 轴上，∴点P 的横坐标为4或-4，这时符合条件的点P 有两个，分别记为P 1,P 2 . 而当x=4时，y=5 3；当x=-4时，y=7， 此时P 1（4，5 3 ）P 2（-4,7） ②当AB 为对角线时，只要线段PQ 与线段AB 互相平分即可 又知点Q 在Y 轴上，且线段AB 中点的横坐标为1 ∴点P 的横坐标为2，这时符合条件的P 只有一个记为P 3 而且当x=2时y=-1 ，此时P 3（2，-1） 综上，满足条件的P 为P 1（4，5 3）P 2（-4,7）P 3（2，-1） 三：解决问题： 问题2：在平面直角坐标系中，已知抛物线经过A （-4，0），B （0，-4），C （2，0）三点． （1）求抛物线的解析式； 《小专题12 二次函数与几何图形综合——特殊图形相关问题》 类型I 特殊三角形问题 1. 如图，已知抛物线与x轴交于A，B两点，并与直线 交于B，C两点，其中点C是直线与y轴的交点，连接AC. （1）求B，C两点的坐标以及抛物线的解析式； （2）求证：△ABC为直角三角形. 2. 如图，已知抛物线与x轴交于A，B两点（点A在点B的右 边），与y轴交于点C. （1）求点A，B，C的坐标； （2）此抛物线的对称轴上是否存在点P，使得△ACP是等腰三角形？若存在，请求出点P的坐标；若不存在，请说明理由. 类型2 特殊四边形问题 3. 如图，已知抛物线y=-x2-2x+3与x轴交于点A，B，与y轴交于点C，顶点为P.若以A，C，P，M为顶点的四边形是平行四边形，求点M的坐标. 参考答案 1.解：（1）直线分别交x轴、y轴于B，C两点，B（4，0），C （0，-2）过B，C两点， 抛物线的解析式为. （2）证明：与x轴负半轴交于A点， .在Rt△AOC中，在Rt△AOC中， 2，. 在Rt△BOC中， . 形。 2. 解：（1）令y=0，得.解得A（4，0），B（-2，0）.令x=0，得y=-2. （2）存在点P，使得△ACP是等腰三角形，设P（1，a），则 . ①当AP=CP时，即 +5，解得a=1.；②当CP=AC时，即， 解得；③当AP=AC时， 即，解得综上所述，满足 条件的点P的坐标为，， 2.解：中，当x=0时， 中，令y=0，即，解得， 顶点P的坐标为（-1，4）. 如图，分别 过△PAC的三个顶点作对边的平行线，三条直线两两相交，产生3个符合条件的点 .，且 . 综上所述，点M的坐标为（-4，1）或 （-2，-1）或（2，7）. 二次函数图象特征与系数关系专题 一、知识要点： 二次函数y=ax2+bx+c(a ≠ 0)系数符号的确定 3、C 由抛物线与y 轴的交点确定：交点在 y 轴的丿正半轴， 则 d 负半轴， 则"O 4、 b2-4ac 的符号由抛物线与 X 轴(或坐标轴)的交点个数确定： 。个交点，b 2-4ac?O ; y = O 时，方程有两个不相等 实数根 ① 与X 轴的交点个数1个交点，b 2-4ac=O ; y =O 时，方程有两个相等实 数根 没有交点，b 2-4ac O; y =O 时，方程无实数根 3个交点，b 2 - 4ac a O ； ② 与坐标轴交点个数 2个交点，b 2 - 4ac = O ; 1 个交点，b 2-4ac O; 5、 根据函数图象的具体情况取特殊值，确定代数式符号： 常见①x=1时，a +b +c 的符号；②x=-1时，a -b+ C 的符号；③x=2时，4a+2b+c 的符号；④ x=-2 时，4a-2b+c 的符号； ......... . K 6、 由对称轴公式X=- 一，可确定2a+b 的符号或对称轴有具体数值是确定相关代数式的符 2a 号；如：X=- =-时，可确定4a-3b 的符号；有时与相关成立的等式或不等式结合，确 2a 3 定运算后代数式的符号。 二、专题练习 ①b 2-4ac >O :② abc >O :③ 8a+c >O ;④ 9a+3b+c V O 2 3、 如图3,二次函数y=ax +bx+c 的图象中，根据图中信息，下列结论正确是( ) 1、a 由抛物线开口方向确定 开口向上=a a O 开口向下=a γ O K 2、b 由对称轴X=-和a 的符号确定 2a So, IaY 0, b 2a Y O 」 a ■ 0, a 0, 2 1.如图1 ,是二次函数y=ax +bx+c ( a ≠0的图象，根据图中信息，下列结论正确是( ) ① a b C >O ; ② b< a+ c ;③2a+b=O :④a +b A 专题九 二次函数与几何图形动点问题 中考目标： 1、 灵活运用二次函数、特殊三角形和四边形相关性质、判定、定理，确定二次函数，判定线与线关系、特殊三角形、四边形及相应的周长、面积、还有存在、最值等问题； 2、 能够通过数形结合，进行建构模型，联想、猜测，运用分类、转化、从特殊到一般归纳等数学思想解 决问题； 3、 运用“动中求静”，找到、运用不变的数、不变的量、不变的关系，建立函数关系及综合应用代数、 几何知识解决问题。 一．考点归纳：特殊图形的定义、性质、判定等，图形的变化：轴对称、平移、旋转（特殊的是中心对称） 二次函数部分的归纳： 1、二次函数的表达式：一般式 ，顶点（ ， ） 对称轴x= ， 还有 式； 2、二次函数的图象是 ，二次函数的性质： 。 二、考点探究 活动一：二次函数与三角形 例1.已知抛物线y ＝ax 2＋bx ＋c （a ＞0）的图象经过点B （12,0）和C （0，－6），对称轴为x ＝2． （1）求该抛物线的解析式； （2）点D 在线段AB 上且AD ＝AC ，若动点P 从A 出发沿线段AB 以每秒1个单位长度的速度匀速运动，同 时另一动点Q 以某一速度从C 出发沿线段CB 匀速运动，问是否存在某一时刻，使线段PQ 被直线CD 垂直 平分？若存在，请求出此时的时间t （秒）和点Q 的运动速度；若不存在，请说明理由； （3）在（2）的结论下，直线x ＝1上是否存在点M 使，△MPQ 为等腰三角形？若存在，请求出所有点M 的 坐标，若不存在，请说明理由． 练习：如图，二次函数y = -x 2+ax +b 的图像与x 轴交于A (-2 1，0)、B (2，0)两点，且与y 轴交于点C ； (1) 求该拋物线的解析式，并判断△ABC 的形状； (2) 在x 轴上方的拋物线上有一点D ，且以A 、C 、D 、B 四点为顶点的四边形是等腰梯形，请直接写出D 点的坐标； (3) 在此拋物线上是否存在点P ，使得以A 、C 、B 、P 四点为顶点的四边形是直角梯形？若存在，求出P 点的坐标；若不存在，说明理由。 跟踪练习：《题型专练》P56 T1；P58 T5 中考考点：二次函数与四边形 例1. 如图，抛物线2 23y x x =--与x 轴交A 、B 两点（A 点在B 点左侧），直线l 与抛物 线交于A 、C 两点，其C 点的横坐标为2．（1）求A 、B 两点的坐标及直线AC 的函数表达式； （2）P 是线段AC 上的一个动点，过P 点作y 轴的平行线交抛物线于E 点，求线段PE 长度的最值； （3）点G 是抛物线上的动点，在x 轴上是否存在点F ，使A 、C 、F 、G 这样的四个点为顶 点的四边形是平行四边形？如果存在，求出所有满足条件的F 点坐标；如果不存在，请说明理由． 跟踪练习：《题型专练》P57 T3；P59 T7 中考考点：二次函数与三角形、四边形的面积 中考数学：二次函数与图形变换 二次函数是初中数学中最精彩的内容之一，也是历年中考的热点和难点。其中，关于函数解析式的确定是非常重要的题型。而今年的中考正是面临新课程改革，教材的内容和学习要求变化较大，其中一个突出的变化就是强化了对图形变换的要求，那么二次函数和图形变化的结合，将是同学们在学习中不可忽视的内容。 图形变换包含平移、轴对称、旋转、位似四种变换，那么二次函数的图像在其图形变化(平移、轴对称、旋转)的过程中，如何完成解析式的确定呢？解决此类问题的方法很多，关键在于解决问题的着眼点。笔者认为最好的方法是用顶点式的方法。因此解题时，先将二次函数解析式化为顶点式，确定其顶点坐标，再根据具体图形变换的特点，确定变化后新的顶点坐标及a值。 1、平移：二次函数图像经过平移变换不会改变图形的形状和开口方向，因此a值不变。顶点位置将会随着整个图像的平移而变化，因此只要按照点的移动规律，求出新的顶点坐标即可确定其解析式。 例1.将二次函数y=x2-2x-3的图像向上平移2个单位，再向右平移1个单位，得到的新的图像解析式为_____ 分析：将y=x2-2x-3化为顶点式y=(x-1)2-4，a值为1，顶点坐标为(1，-4)，将其图像向上平移2个单位，再向右平移1个单位，那么顶点也会相应移动，其坐标为(2，-2),由于平移不改变二次函数的图像的形状和开口方向，因此a值不变，故平移后的解析式为y=(x-2)2-2。 2、轴对称：此图形变换包括x轴对称和关于y轴对称两种方式。 二次函数图像关于x轴对称的图像，其形状不变，但开口方向相反，因此a值为原来的相反数。顶点位置改变，只要根据关于x轴对称的点的坐标特征求出新的顶点坐标，即可确定其解析式。 二次函数图像关于y轴对称的图像，其形状和开口方向都不变，因此a 值不变。但是顶点位置会改变，只要根据关于y轴对称的点的坐标特征求出新的顶点坐标，即可确定其解析式。 例2.求抛物线y=x2-2x-3关于x轴以及y轴对称的抛物线的解析式。实验一、复变函数与特殊函数图形的绘制
2021年二次函数与特殊图形的存在性问题(学生版+解析版)
专题04 二次函数与特殊图形的存在性问题(连云港26题无锡27题淮安28题等)(解析版)
一些常用函数及其泰勒(Taylor)展开式的图像
二次函数与几何图形结合题及答案
中考数学复习专题：二次函数中特殊图形的存在性问题的分析方法
实验1_函数的图形
9年级4.3—二次函数背景下的特殊图形问题
一些特殊函数
二次函数与几何图形结合题型总结
二次函数与几何图形综合题(可编辑修改word版)
几种特殊函数的图象及性质
专题二次函数与几何图形
二次函数与几何图形的综合题
二次函数与几何图形的综合问题
小专题12__二次函数与几何图形综合-特殊图形相关问题
二次函数图象特征与系数关系专题
二次函数与几何图形动点问题
中考数学：二次函数与图形变换